ON THE UNDECIDABILITY OF THE FREENESS OF INTEGER MATRIX SEMIGROUPS
From MaRDI portal
Publication:5758380
DOI10.1142/S0218196791000146zbMath0724.20036MaRDI QIDQ5758380
Wade Satterfield, David A. Klarner, Jean-Camille Birget
Publication date: 1992
Published in: International Journal of Algebra and Computation (Search for Journal in Brave)
free semigroups; integer matrices; generators and relations; Post correspondence problem; undecidable problems
20M20: Semigroups of transformations, relations, partitions, etc.
20M05: Free semigroups, generators and relations, word problems
15A30: Algebraic systems of matrices
Related Items
Unnamed Item, ON THE UNDECIDABILITY OF FREENESS OF MATRIX SEMIGROUPS, On equality of Hausdorff and affinity dimensions, via self-affine measures on positive subsystems, Relations in the semigroup of 2 × 2 upper-triangular matrices, Freeness Problem for Matrix Semigroups of Parikh Matrices, Substitution invariant Sturmian words and binary trees, A survey of computational complexity results in systems and control, Products of matrices and recursively enumerable sets, Examples of undecidable problems for 2-generator matrix semigroups, Automaton semigroups and groups: on the undecidability of problems related to freeness and finiteness, On injectivity of quantum finite automata, The freeness problem over matrix semigroups and bounded languages, On the problem of freeness of multiplicative matrix semigroups, Freeness properties of weighted and probabilistic automata over bounded languages, Finding binomials in polynomial ideals, On the decidability of semigroup freeness, Matrix Semigroup Freeness Problems in SL $$(2,\mathbb {Z})$$, Vector Ambiguity and Freeness Problems in SL $$(2,\mathbb {Z})$$, UNDECIDABILITY BOUNDS FOR INTEGER MATRICES USING CLAUS INSTANCES, On free semigroups of affine maps on the real line, MATRIX EQUATIONS AND HILBERT'S TENTH PROBLEM, NUMBER SYSTEMS AND THE INJECTIVITY PROBLEM FOR MATRIX REPRESENTATIONS OF FREE MONOIDS, Post Correspondence Problem and Small Dimensional Matrices
