ON THE UNDECIDABILITY OF FREENESS OF MATRIX SEMIGROUPS
From MaRDI portal
Publication:4513303
DOI10.1142/S0218196799000199zbMath1029.20027MaRDI QIDQ4513303
Juhani Karhumäki, Julien Cassaigne, Tero J.Harju
Publication date: 7 November 2000
Published in: International Journal of Algebra and Computation (Search for Journal in Brave)
undecidability; semigroups of matrices; finitely presented semigroups; Post correspondence problem; freeness problem
20M20: Semigroups of transformations, relations, partitions, etc.
20M05: Free semigroups, generators and relations, word problems
03D35: Undecidability and degrees of sets of sentences
Related Items
Unnamed Item, On equality of Hausdorff and affinity dimensions, via self-affine measures on positive subsystems, Some decision problems on integer matrices, Unnamed Item, 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, Remarks concerning the freeness problem over morphism and matrix semigroups., Compositions of linear functions and applications to hashing, Products of matrices and recursively enumerable sets, A Kraft-McMillan inequality for free semigroups of upper-triangular matrices, Reachability problems in quaternion matrix and rotation semigroups, More secure version of a Cayley hash function, Vector and scalar reachability problems in \(\operatorname{SL}(2, \mathbb{Z})\), Decision problems for semi-Thue systems with a few rules, Polynomially ambiguous probabilistic automata on restricted languages, 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, A characterization of free pairs of upper triangular free monoid morphisms, On undecidability bounds for matrix decision problems, Improved matrix pair undecidability results, 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 THE UNDECIDABILITY OF THE IDENTITY CORRESPONDENCE PROBLEM AND ITS APPLICATIONS FOR WORD AND MATRIX SEMIGROUPS, Reachability Problems for One-Dimensional Piecewise Affine Maps, 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
Cites Work
