REDUCTION TREE OF THE BINARY GENERALIZED POST CORRESPONDENCE PROBLEM

DOI10.1142/S0129054111008143zbMath1211.68233OpenAlexW2011990179MaRDI QIDQ3086251

Vesa Halava, Štěpán Holub

Publication date: 30 March 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/s0129054111008143

Mathematics Subject Classification ID

Combinatorics on words (68R15) Formal languages and automata (68Q45) Decidability of theories and sets of sentences (03B25)

Related Items (4)

Binary Generalized PCP for Two Periodic Morphisms is Decidable in Polynomial Time ⋮ Large Simple Binary Equality Words ⋮ Periodicity forcing words ⋮ LARGE SIMPLE BINARY EQUALITY WORDS

Cites Work

• Unnamed Item
• Unnamed Item
• The (generalized) Post correspondence problem with lists consisting of two words is decidable
• Binary (generalized) Post Correspondence Problem
• Decision problems for semi-Thue systems with a few rules
• Binary equality sets are generated by two words
• A variant of a recursively unsolvable problem

This page was built for publication: REDUCTION TREE OF THE BINARY GENERALIZED POST CORRESPONDENCE PROBLEM