More decidable instances of Post's correspondence problem: beyond counting
From MaRDI portal
Publication:963345
DOI10.1016/J.IPL.2007.11.002zbMATH Open1186.68266OpenAlexW1986342569MaRDI QIDQ963345FDOQ963345
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
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
- Title not available (Why is that?)
- A variant of a recursively unsolvable problem
- Generalized Parikh mappings and homomorphisms
- A useful device for showing the solvability of some decision problems
- The (generalized) Post correspondence problem with lists consisting of two words is decidable
- A Remark on Code Sets and Context-Free Languages
- Extension of the decidability of the marked PCP to instances with unique blocks
- Generalized Post correspondence problem for marked morphisms
- Marked PCP is decidable
Cited In (2)
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)
