Post Embedding Problem Is Not Primitive Recursive, with Applications to Channel Systems

DOI10.1007/978-3-540-77050-3_22zbMath1136.03030OpenAlexW1528258327WikidataQ56095061 ScholiaQ56095061MaRDI QIDQ5458840

Pierre Chambart, Philippe Schnoebelen

Publication date: 24 April 2008

Published in: FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-77050-3_22

zbMATH Keywords

Post correspondence problemLossy channel systemsHigman's Lemma

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Decidability of theories and sets of sentences (03B25) Word problems, etc. in computability and recursion theory (03D40) Thue and Post systems, etc. (03D03)

Related Items

Zeno, Hercules, and the Hydra ⋮ Mixing Lossy and Perfect Fifo Channels ⋮ On the Reachability Analysis of Acyclic Networks of Pushdown Systems ⋮ Multiply-Recursive Upper Bounds with Higman’s Lemma ⋮ The ω-Regular Post Embedding Problem ⋮ Complexity Hierarchies beyond Elementary ⋮ Rational subsets and submonoids of wreath products. ⋮ Generalized Post embedding problems

Cites Work

• Unnamed Item
• Unnamed Item
• On some variants of Post's correspondence problem
• Simulating perfect channels with probabilistic lossy channels
• Verifying lossy channel systems has nonprimitive recursive complexity.
• Verifying programs with unreliable channels
• Non-primitive recursive decidability of products of modal logics with expanding domains
• On the decidability and complexity of Metric Temporal Logic over finite words
• Automated Deduction – CADE-20
• Foundations of Software Science and Computational Structures
• Automata, Languages and Programming
• Marked PCP is decidable