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