ON THE UNDECIDABILITY OF THE IDENTITY CORRESPONDENCE PROBLEM AND ITS APPLICATIONS FOR WORD AND MATRIX SEMIGROUPS

DOI10.1142/S0129054110007660zbMath1209.68393WikidataQ56095063 ScholiaQ56095063MaRDI QIDQ3069735

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

undecidability; matrix semigroups; combinatorics on words; Post's correspondence problem; group problem

Mathematics Subject Classification ID

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