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
Some decision problems on integer matrices, 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, Decision problems for semi-Thue systems with a few rules, The freeness problem over matrix semigroups and bounded languages, On the problem of freeness of multiplicative matrix semigroups, On undecidability bounds for matrix decision problems, Improved matrix pair undecidability results, On the decidability of semigroup freeness, UNDECIDABILITY BOUNDS FOR INTEGER MATRICES USING CLAUS INSTANCES, ON THE UNDECIDABILITY OF THE IDENTITY CORRESPONDENCE PROBLEM AND ITS APPLICATIONS FOR WORD AND MATRIX SEMIGROUPS, 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
