On Semigroups of Two-Dimensional Upper-Triangular Integer Matrices
share
We analyze algorithmic problems in finitely generated semigroups of two-dimensional upper-triangular integer matrices. These semigroup problems are tightly connected with problems about compositions of affine functions over one variable. Building on a variety of techniques from recent years, we obtain a number of complexity results, including NP-completeness of the mortality problem for matrices with determinants +1 and 0.
READ FULL TEXT