On the problem of freeness of multiplicative matrix semigroups

DOI10.1016/J.TCS.2009.12.005MaRDI QIDQ2268869zbMATH OpenOpenAlexFDO

Authors Paweł Gawrychowski, Marin Guţan, Andrzej Kisielewicz

Publication date 9 March 2010

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2009.12.005

zbMATH Keywords

freenessmatrix semigroupsnumerical algorithmtriangular integer matrices

Mathematics Subject Classification ID

Algebraic systems of matrices (15A30) Matrices of integers (15B36) Semigroups of transformations, relations, partitions, etc. (20M20)

Review text

The authors consider the freeness of multiplicative matrix semigroups generated by triangular integer matrices of order \(2\) being nonsingular. The problem is reduced to verify if equations involving powers of such matrices, where the sum of powers match, are satisfied. Considering that the matrices are noncommutative, otherwise the problem is trivial, the only possible different is the element \((1,2)\) of the product. A scalar algorithm is developed to test the equality of that element in both sides of the equation.

Recommendations

• Freeness problem for matrix semigroups of Parikh matrices
• Remarks concerning the freeness problem over morphism and matrix semigroups.
• ON THE UNDECIDABILITY OF FREENESS OF MATRIX SEMIGROUPS
• ON THE UNDECIDABILITY OF THE FREENESS OF INTEGER MATRIX SEMIGROUPS
• On some free semigroups, generated by matrices
• Matrix semigroup freeness problems in \(\mathrm{SL}(2,\mathbb {Z})\)
• Multiplicative preservers on semigroups of matrices
• scientific article; zbMATH DE number 4036083
• On free affine semigroups

Cites work

• Examples of undecidable problems for 2-generator matrix semigroups
• On the decidability of semigroup freeness.
• ON THE UNDECIDABILITY OF FREENESS OF MATRIX SEMIGROUPS
• ON THE UNDECIDABILITY OF THE FREENESS OF INTEGER MATRIX SEMIGROUPS
• Some decision problems on integer matrices
• The mortality problem for matrices of low dimensions

Cited in

(9)

• The freeness problem over matrix semigroups and bounded languages
• On the decidability of semigroup freeness.
• On some free semigroups, generated by matrices
• Matrix semigroup freeness problems in \(\mathrm{SL}(2,\mathbb {Z})\)
• ON THE UNDECIDABILITY OF FREENESS OF MATRIX SEMIGROUPS
• On equality of Hausdorff and affinity dimensions, via self-affine measures on positive subsystems
• A Kraft-McMillan inequality for free semigroups of upper-triangular matrices
• Relations in the semigroup of \(2\times 2\) upper-triangular matrices
• Freeness problem for matrix semigroups of Parikh matrices

This page was built for publication: On the problem of freeness of multiplicative matrix semigroups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2268869)