ON THE UNDECIDABILITY OF THE IDENTITY CORRESPONDENCE PROBLEM AND ITS APPLICATIONS FOR WORD AND MATRIX SEMIGROUPS
From MaRDI portal
Publication:3069735
DOI10.1142/S0129054110007660zbMath1209.68393WikidataQ56095063 ScholiaQ56095063MaRDI QIDQ3069735
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
undecidability; matrix semigroups; combinatorics on words; Post's correspondence problem; group problem
68R15: Combinatorics on words
Related Items
Unnamed Item, On the Identity Problem for the Special Linear Group and the Heisenberg Group., On Reachability Problems for Low-Dimensional Matrix Semigroups, Acceptance Ambiguity for Quantum Automata, Weighted automata on infinite words in the context of attacker-defender games, Unambiguous injective morphisms in free groups, Automaton semigroups and groups: on the undecidability of problems related to freeness and finiteness, On injectivity of quantum finite automata, Matrix Semigroup Freeness Problems in SL $$(2,\mathbb {Z})$$, Weighted Automata on Infinite Words in the Context of Attacker-Defender Games, Ambiguity of Morphisms in a Free Group
Cites Work
- On the membership of invertible diagonal and scalar matrices
- Reachability problems in quaternion matrix and rotation semigroups
- On deciding whether a monoid is a free monoid or is a group
- A class of free rotation groups
- The boundedness of all products of a pair of matrices is undecidable
- Decision problems for semi-Thue systems with a few rules
- On undecidability bounds for matrix decision problems
- UNDECIDABILITY BOUNDS FOR INTEGER MATRICES USING CLAUS INSTANCES
- ON THE UNDECIDABILITY OF FREENESS OF MATRIX SEMIGROUPS
- Some decision problems on integer matrices
- Decidable and Undecidable Problems about Quantum Automata
- A variant of a recursively unsolvable problem