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

DOI10.1142/S0129054110007660zbMath1209.68393OpenAlexW2050829703WikidataQ56095063 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

undecidabilitymatrix semigroupscombinatorics on wordsPost's correspondence problemgroup problem

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Related Items (12)

Ambiguity of Morphisms in a Free Group ⋮ Weighted Automata on Infinite Words in the Context of Attacker-Defender Games ⋮ Automaton semigroups and groups: on the undecidability of problems related to freeness and finiteness ⋮ The membership problem for subsemigroups of \(\operatorname{GL}_2(\mathbb{Z})\) is \textbf{NP}-complete ⋮ Matrix Semigroup Freeness Problems in SL $$(2,\mathbb {Z})$$ ⋮ On injectivity of quantum finite automata ⋮ On the Identity Problem for the Special Linear Group and the Heisenberg Group. ⋮ Weighted automata on infinite words in the context of attacker-defender games ⋮ Unnamed Item ⋮ On Reachability Problems for Low-Dimensional Matrix Semigroups ⋮ Acceptance Ambiguity for Quantum Automata ⋮ Unambiguous injective morphisms in free groups

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

This page was built for publication: ON THE UNDECIDABILITY OF THE IDENTITY CORRESPONDENCE PROBLEM AND ITS APPLICATIONS FOR WORD AND MATRIX SEMIGROUPS