ON THE UNDECIDABILITY OF THE FREENESS OF INTEGER MATRIX SEMIGROUPS

DOI10.1142/S0218196791000146MaRDI QIDQ5758380zbMATH OpenOpenAlexFDO

Authors Wade Satterfield, David A. Klarner, J.-C. Birget

Publication date 1992

Published in International Journal of Algebra and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s0218196791000146

zbMATH Keywords

integer matricesPost correspondence problemgenerators and relationsfree semigroupsundecidable problems

Mathematics Subject Classification ID

Semigroups of transformations, relations, partitions, etc. (20M20) Algebraic systems of matrices (15A30) Free semigroups, generators and relations, word problems (20M05)

Recommendations

• ON THE UNDECIDABILITY OF FREENESS OF MATRIX SEMIGROUPS
• The symmetric Post correspondence problem, and errata for the freeness problem for matrix semigroups
• Remarks concerning the freeness problem over morphism and matrix semigroups.
• On Markov's undecidability theorem for integer matrices.
• The freeness problem over matrix semigroups and bounded languages

Cited in

(34)

• The freeness problem over matrix semigroups and bounded languages
• On the problem of freeness of multiplicative matrix semigroups
• scientific article; zbMATH DE number 6902897 (Why is no real title available?)
• Some decision problems on integer matrices
• Post Correspondence Problem and Small Dimensional Matrices
• On the undecidability of the identity correspondence problem and its applications for word and matrix semigroups
• Undecidability in matrices over Laurent polynomials.
• A note on the emptiness of semigroup intersections
• ON THE UNDECIDABILITY OF FREENESS OF MATRIX SEMIGROUPS
• Matrix semigroup freeness problems in \(\mathrm{SL}(2,\mathbb {Z})\)
• Vector ambiguity and freeness problems in \(\mathrm{SL} (2,\mathbb {Z})\)
• On injectivity of quantum finite automata
• MATRIX EQUATIONS AND HILBERT'S TENTH PROBLEM
• Remarks concerning the freeness problem over morphism and matrix semigroups.
• Finding binomials in polynomial ideals
• A survey of computational complexity results in systems and control
• Automaton semigroups and groups: on the undecidability of problems related to freeness and finiteness
• The symmetric Post correspondence problem, and errata for the freeness problem for matrix semigroups
• Relations in the semigroup of \(2\times 2\) upper-triangular matrices
• Freeness properties of weighted and probabilistic automata over bounded languages
• Examples of undecidable problems for 2-generator matrix semigroups
• Products of matrices and recursively enumerable sets
• Undecidability bounds for integer matrices using Claus instances
• NUMBER SYSTEMS AND THE INJECTIVITY PROBLEM FOR MATRIX REPRESENTATIONS OF FREE MONOIDS
• List of problems on discrete subgroups of Lie groups and their computational aspects
• Acceptance Ambiguity for Quantum Automata
• On free semigroups of affine maps on the real line
• Substitution invariant Sturmian words and binary trees
• The ubiquity of free subsemigroups of infinite triangular matrices
• Periodic and Infinite Traces in Matrix Semigroups
• On the decidability of semigroup freeness.
• On Markov's undecidability theorem for integer matrices.
• Freeness problem for matrix semigroups of Parikh matrices
• On equality of Hausdorff and affinity dimensions, via self-affine measures on positive subsystems

This page was built for publication: ON THE UNDECIDABILITY OF THE FREENESS OF INTEGER MATRIX SEMIGROUPS

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