Extension of the decidability of the marked PCP to instances with unique blocks
DOI10.1016/J.TCS.2007.03.024zbMATH Open1119.03041OpenAlexW2142786187MaRDI QIDQ2373757FDOQ2373757
Authors: Vesa Halava, Tero Harju, Juhani Karhumäki, Michel Latteux 
Publication date: 16 July 2007
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2007.03.024
Recommendations
unique continuationdecidabilityPost correspondence problemmarked morphisminfinite Post correspondence problemunique block
Decidability of theories and sets of sentences (03B25) Thue and Post systems, etc. (03D03) Word problems, etc. in computability and recursion theory (03D40)
Cites Work
- A variant of a recursively unsolvable problem
- Decision problems for semi-Thue systems with a few rules
- Title not available (Why is that?)
- Title not available (Why is that?)
- The (generalized) Post correspondence problem with lists consisting of two words is decidable
- Undecidability of infinite post correspondence problem for instances of Size 9
- The structure of infinite solutions of marked and binary Post correspondence problems
- Decidability of the binary infinite Post Correspondence Problem
- Generalized Post correspondence problem for marked morphisms
- Marked PCP is decidable
- Title not available (Why is that?)
- Binary (generalized) Post Correspondence Problem
- Title not available (Why is that?)
Cited In (4)
This page was built for publication: Extension of the decidability of the marked PCP to instances with unique blocks
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2373757)
