ON THE UNDECIDABILITY OF FREENESS OF MATRIX SEMIGROUPS
From MaRDI portal
Publication:4513303
DOI10.1142/S0218196799000199zbMath1029.20027OpenAlexW2008458160MaRDI 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)
Full work available at URL: https://doi.org/10.1142/s0218196799000199
undecidabilitysemigroups of matricesfinitely presented semigroupsPost correspondence problemfreeness problem
Semigroups of transformations, relations, partitions, etc. (20M20) Free semigroups, generators and relations, word problems (20M05) Undecidability and degrees of sets of sentences (03D35)
Related Items
Polynomially ambiguous probabilistic automata on restricted languages, Freeness and 𝑆-arithmeticity of rational Möbius groups, Remarks concerning the freeness problem over morphism and matrix semigroups., On the decidability of semigroup freeness, Reachability Problems for One-Dimensional Piecewise Affine Maps, More secure version of a Cayley hash function, Improved matrix pair undecidability results, Compositions of linear functions and applications to hashing, The symmetric Post Correspondence Problem, and errata for the freeness problem for matrix semigroups, A characterization of free pairs of upper triangular free monoid morphisms, EDT0L grammars with only one variable have tractable generating functions, The membership problem for subsemigroups of \(\operatorname{GL}_2(\mathbb{Z})\) is \textbf{NP}-complete, 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, A Kraft-McMillan inequality for free semigroups of upper-triangular matrices, On injectivity of quantum finite automata, On the Identity Problem for the Special Linear Group and the Heisenberg Group., Vector and scalar reachability problems in \(\operatorname{SL}(2, \mathbb{Z})\), On equality of Hausdorff and affinity dimensions, via self-affine measures on positive subsystems, On undecidability bounds for matrix decision problems, Reachability problems in quaternion matrix and rotation semigroups, Freeness Problem for Matrix Semigroups of Parikh Matrices, The freeness problem over matrix semigroups and bounded languages, Decision problems for semi-Thue systems with a few rules, On the problem of freeness of multiplicative matrix semigroups, Some decision problems on integer matrices, 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, ON THE UNDECIDABILITY OF THE IDENTITY CORRESPONDENCE PROBLEM AND ITS APPLICATIONS FOR WORD AND MATRIX SEMIGROUPS, 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, Polynomially Ambiguous Probabilistic Automata on Restricted Languages, Acceptance Ambiguity for Quantum Automata
Cites Work
