ON THE UNDECIDABILITY OF THE FREENESS OF INTEGER MATRIX SEMIGROUPS
From MaRDI portal
Publication:5758380
DOI10.1142/S0218196791000146zbMath0724.20036OpenAlexW1978026916MaRDI 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)
Full work available at URL: https://doi.org/10.1142/s0218196791000146
free semigroupsinteger matricesgenerators and relationsPost correspondence problemundecidable problems
Semigroups of transformations, relations, partitions, etc. (20M20) Free semigroups, generators and relations, word problems (20M05) Algebraic systems of matrices (15A30)
Related Items (26)
List of problems on discrete subgroups of Lie groups and their computational aspects ⋮ On the decidability of semigroup freeness ⋮ Finding binomials in polynomial ideals ⋮ The symmetric Post Correspondence Problem, and errata for the freeness problem for matrix semigroups ⋮ Automaton semigroups and groups: on the undecidability of problems related to freeness and finiteness ⋮ Matrix Semigroup Freeness Problems in SL $$(2,\mathbb {Z})$$ ⋮ Vector Ambiguity and Freeness Problems in SL $$(2,\mathbb {Z})$$ ⋮ Products of matrices and recursively enumerable sets ⋮ On injectivity of quantum finite automata ⋮ On equality of Hausdorff and affinity dimensions, via self-affine measures on positive subsystems ⋮ Freeness Problem for Matrix Semigroups of Parikh Matrices ⋮ A survey of computational complexity results in systems and control ⋮ The freeness problem over matrix semigroups and bounded languages ⋮ On the problem of freeness of multiplicative matrix semigroups ⋮ MATRIX EQUATIONS AND HILBERT'S TENTH PROBLEM ⋮ Freeness properties of weighted and probabilistic automata over bounded languages ⋮ UNDECIDABILITY BOUNDS FOR INTEGER MATRICES USING CLAUS INSTANCES ⋮ Substitution invariant Sturmian words and binary trees ⋮ Unnamed Item ⋮ Relations in the semigroup of 2 × 2 upper-triangular matrices ⋮ NUMBER SYSTEMS AND THE INJECTIVITY PROBLEM FOR MATRIX REPRESENTATIONS OF FREE MONOIDS ⋮ Post Correspondence Problem and Small Dimensional Matrices ⋮ On free semigroups of affine maps on the real line ⋮ Acceptance Ambiguity for Quantum Automata ⋮ Examples of undecidable problems for 2-generator matrix semigroups ⋮ ON THE UNDECIDABILITY OF FREENESS OF MATRIX SEMIGROUPS
This page was built for publication: ON THE UNDECIDABILITY OF THE FREENESS OF INTEGER MATRIX SEMIGROUPS
