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

DOI10.1142/S0129054110007660zbMath1209.68393WikidataQ56095063 ScholiaQ56095063MaRDI QIDQ3069735

Igor Potapov, Paul C. Bell

Publication date: 19 January 2011

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

zbMATH Keywords

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

Mathematics Subject Classification ID

68R15: Combinatorics on words

Related Items

Weighted automata on infinite words in the context of attacker-defender games, 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