On the undecidability of the identity correspondence problem and its applications for word and matrix semigroups

DOI10.1142/S0129054110007660MaRDI QIDQ3069735zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Paul C. Bell, Igor Potapov

Publication date 19 January 2011

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s0129054110007660

zbMATH Keywords

combinatorics on wordsundecidabilitymatrix semigroupsgroup problemPost's correspondence problem

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Recommendations

• The Identity Correspondence Problem and Its Applications
• ON THE UNDECIDABILITY OF THE FREENESS OF INTEGER MATRIX SEMIGROUPS
• Examples of undecidable problems for 2-generator matrix semigroups
• On the computational complexity of matrix semigroup problems
• Periodic and Infinite Traces in Matrix Semigroups

Cites work

• A class of free rotation groups
• A variant of a recursively unsolvable problem
• Decidable and Undecidable Problems about Quantum Automata
• Decision problems for semi-Thue systems with a few rules
• ON THE UNDECIDABILITY OF FREENESS OF MATRIX SEMIGROUPS
• On deciding whether a monoid is a free monoid or is a group
• On the membership of invertible diagonal and scalar matrices
• On undecidability bounds for matrix decision problems
• Reachability problems in quaternion matrix and rotation semigroups
• Some decision problems on integer matrices
• The boundedness of all products of a pair of matrices is undecidable
• Undecidability bounds for integer matrices using Claus instances

Cited in

(25)

• Developments in Language Theory
• The identity problem in the special affine group of \(\mathbb{Z}^2\)
• On simulating Turing machines with matrix semigroups with integrality tests
• ON THE UNDECIDABILITY OF FREENESS OF MATRIX SEMIGROUPS
• Matrix semigroup freeness problems in \(\mathrm{SL}(2,\mathbb {Z})\)
• On the Identity Problem for the Special Linear Group and the Heisenberg Group.
• Unambiguous injective morphisms in free groups
• On injectivity of quantum finite automata
• Weighted automata on infinite words in the context of attacker-defender games
• Membership problems in infinite groups
• The membership problem for subsemigroups of \(\operatorname{GL}_2(\mathbb{Z})\) is \textbf{NP}-complete
• Automaton semigroups and groups: on the undecidability of problems related to freeness and finiteness
• The Identity Correspondence Problem and Its Applications
• On the identity and group problems for complex Heisenberg matrices
• Membership problems in braid groups and Artin groups
• On the computational complexity of matrix semigroup problems
• Weighted automata on infinite words in the context of attacker-defender games
• Ordering groups and the identity problem
• On the membership of invertible diagonal and scalar matrices
• Acceptance Ambiguity for Quantum Automata
• Semigroup intersection problems in the Heisenberg groups
• Ambiguity of morphisms in a free group
• On Reachability Problems for Low-Dimensional Matrix Semigroups
• scientific article; zbMATH DE number 7204378 (Why is no real title available?)
• Periodic and Infinite Traces in Matrix Semigroups

This page was built for publication: On the undecidability of the identity correspondence problem and its applications for word and matrix semigroups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3069735)