On the undecidability of the identity correspondence problem and its applications for word and matrix semigroups
From MaRDI portal
Publication:3069735
DOI10.1142/S0129054110007660zbMATH Open1209.68393DBLPjournals/ijfcs/BellP10OpenAlexW2050829703WikidataQ56095063 ScholiaQ56095063MaRDI QIDQ3069735FDOQ3069735
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
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 variant of a recursively unsolvable problem
- The boundedness of all products of a pair of matrices is undecidable
- Decision problems for semi-Thue systems with a few rules
- UNDECIDABILITY BOUNDS FOR INTEGER MATRICES USING CLAUS INSTANCES
- ON THE UNDECIDABILITY OF FREENESS OF MATRIX SEMIGROUPS
- Reachability problems in quaternion matrix and rotation semigroups
- A class of free rotation groups
- On the membership of invertible diagonal and scalar matrices
- Decidable and Undecidable Problems about Quantum Automata
- On deciding whether a monoid is a free monoid or is a group
- Some decision problems on integer matrices
- On undecidability bounds for matrix decision problems
Cited In (20)
- Developments in Language Theory
- On simulating Turing machines with matrix semigroups with integrality tests
- Ambiguity of Morphisms in a Free Group
- ON THE UNDECIDABILITY OF FREENESS OF MATRIX SEMIGROUPS
- 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
- The membership problem for subsemigroups of \(\operatorname{GL}_2(\mathbb{Z})\) is \textbf{NP}-complete
- Matrix Semigroup Freeness Problems in SL $$(2,\mathbb {Z})$$
- 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
- On the membership of invertible diagonal and scalar matrices
- Acceptance Ambiguity for Quantum Automata
- Semigroup intersection problems in the Heisenberg groups
- On Reachability Problems for Low-Dimensional Matrix Semigroups
- Title not available (Why is that?)
- Periodic and Infinite Traces in Matrix Semigroups
- Weighted Automata on Infinite Words in the Context of Attacker-Defender Games
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)
