More decidable instances of Post's correspondence problem: beyond counting

DOI10.1016/J.IPL.2007.11.002MaRDI QIDQ963345zbMATH OpenOpenAlexFDO

Authors Mirko Rahn

Publication date 19 April 2010

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2007.11.002

zbMATH Keywords

decidabilitycombinatorial problemscontext-free languagePost correspondence problem

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• On some variants of Post's correspondence problem
• Decidability of the binary infinite Post Correspondence Problem
• Publication:4729772
• scientific article; zbMATH DE number 2051181
• The exact complexity of the infinite Post Correspondence Problem
• On the \(n\)-permutation Post correspondence problem
• P, NP, and the Post correspondence problem
• On simplest possible solutions for Post Correspondence Problems
• Post's correspondence problem: from computer science to algebra
• scientific article; zbMATH DE number 1339972

Cites work

• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• A Remark on Code Sets and Context-Free Languages
• A useful device for showing the solvability of some decision problems
• A variant of a recursively unsolvable problem
• Extension of the decidability of the marked PCP to instances with unique blocks
• Generalized Parikh mappings and homomorphisms
• Generalized Post correspondence problem for marked morphisms
• Marked PCP is decidable
• The (generalized) Post correspondence problem with lists consisting of two words is decidable

Cited in

(2)

• Undecidability of infinite post correspondence problem for instances of Size 9
• Undecidability of infinite Post correspondence problem for instances of size 8

This page was built for publication: More decidable instances of Post's correspondence problem: beyond counting

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q963345)