ON THE UNDECIDABILITY OF THE FREENESS OF INTEGER MATRIX SEMIGROUPS

DOI10.1142/S0218196791000146zbMATH Open0724.20036OpenAlexW1978026916MaRDI QIDQ5758380FDOQ5758380

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

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

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)

Cited In (34)

• The freeness problem over matrix semigroups and bounded languages
• On the problem of freeness of multiplicative matrix semigroups
• Title not available (Why is that?)
• Some decision problems on integer matrices
• Post Correspondence Problem and Small Dimensional Matrices
• A note on the emptiness of semigroup intersections
• On the undecidability of the identity correspondence problem and its applications for word and matrix semigroups
• ON THE UNDECIDABILITY OF FREENESS OF MATRIX SEMIGROUPS
• Matrix semigroup freeness problems in \(\mathrm{SL}(2,\mathbb {Z})\)
• Undecidability in matrices over Laurent polynomials.
• Vector ambiguity and freeness problems in \(\mathrm{SL} (2,\mathbb {Z})\)
• MATRIX EQUATIONS AND HILBERT'S TENTH PROBLEM
• On injectivity of quantum finite automata
• 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
• Periodic and Infinite Traces in Matrix Semigroups
• The ubiquity of free subsemigroups of infinite triangular matrices
• 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)