The (generalized) Post correspondence problem with lists consisting of two words is decidable

DOI10.1016/0304-3975(89)90080-7zbMath0493.68076OpenAlexW1985369251MaRDI QIDQ1168746

Juhani Karhumäki, Andrzej Ehrenfeucht, Grzegorz Rozenberg

Publication date: 1982

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(89)90080-7

zbMATH Keywords

Turing machinesword problemdecidabilityhomomorphic equality

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Free semigroups, generators and relations, word problems (20M05) Semigroups in automata theory, linguistics, etc. (20M35) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Word problems, etc. in computability and recursion theory (03D40)

Related Items (35)

Sur la combinatoire des codes à deux mots. (On the combinatorics of two-word codes) ⋮ Automatic sequences of rank two ⋮ Parsimonious computational completeness ⋮ Variations on the post correspondence problem for free groups ⋮ Extension of the decidability of the marked PCP to instances with unique blocks ⋮ On the decidability of semigroup freeness ⋮ Undecidability of infinite post correspondence problem for instances of size 8 ⋮ Flatwords and Post Correspondence Problem ⋮ Representations of language families by homomorphic equality operations and generalized equality sets ⋮ The origins of combinatorics on words ⋮ Binary Generalized PCP for Two Periodic Morphisms is Decidable in Polynomial Time ⋮ Post's correspondence problem: from computer science to algebra ⋮ On bi-infinite and conjugate post correspondence problems ⋮ Post's Correspondence Problem for hyperbolic and virtually nilpotent groups ⋮ Decidability of the binary infinite Post Correspondence Problem ⋮ Large Simple Binary Equality Words ⋮ GENERALIZED POST CORRESPONDENCE PROBLEM FOR MARKED MORPHISMS ⋮ The Post correspondence problem over a unary alphabet ⋮ BINARY MORPHISMS WITH STABLE SUFFIX COMPLEXITY ⋮ More decidable instances of Post's correspondence problem: beyond counting ⋮ LARGE SIMPLE BINARY EQUALITY WORDS ⋮ Decision problems for semi-Thue systems with a few rules ⋮ Post correspondence problem for short words ⋮ Marked PCP is decidable ⋮ Binary equality words with two $b$'s ⋮ REDUCTION TREE OF THE BINARY GENERALIZED POST CORRESPONDENCE PROBLEM ⋮ Post Correspondence Problem and Small Dimensional Matrices ⋮ Frontier between decidability and undecidability: A survey ⋮ Undecidability of infinite post correspondence problem for instances of Size 9 ⋮ On some variants of Post's correspondence problem ⋮ On binary equality sets and a solution to the test set conjecture in the binary case ⋮ The Ehrenfeucht conjecture: A compactness claim for finitely generated free monoids ⋮ Test sets for morphisms with bounded delay ⋮ Binary (generalized) Post Correspondence Problem ⋮ Binary equality sets are generated by two words

Cites Work

• Equality Sets and Complexity Classes
• Fixed Point Languages, Equality Languages, and Representation of Recursively Enumerable Languages
• A Purely Homomorphic Characterization of Recursively Enumerable Sets
• A variant of a recursively unsolvable problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The (generalized) Post correspondence problem with lists consisting of two words is decidable