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

DOI10.1007/978-3-540-77050-3_22MaRDI QIDQ5458840zbMATH OpenOpenAlexWikidataFDO

Authors 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) Decidability of theories and sets of sentences (03B25) Thue and Post systems, etc. (03D03) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Word problems, etc. in computability and recursion theory (03D40)

Recommendations

• The ω-Regular Post Embedding Problem
• Pumping and counting on the regular Post embedding problem
• On reachability for unidirectional channel systems extended with regular tests

Cites work

• scientific article; zbMATH DE number 1809622 (Why is no real title available?)
• scientific article; zbMATH DE number 2242597 (Why is no real title available?)
• Automata, Languages and Programming
• Automated Deduction – CADE-20
• Foundations of Software Science and Computational Structures
• Marked PCP is decidable
• Non-primitive recursive decidability of products of modal logics with expanding domains
• On some variants of Post's correspondence problem
• On the decidability and complexity of Metric Temporal Logic over finite words
• Simulating perfect channels with probabilistic lossy channels
• Verifying lossy channel systems has nonprimitive recursive complexity.
• Verifying programs with unreliable channels

Cited in

(9)

• Mixing Lossy and Perfect Fifo Channels
• On the Reachability Analysis of Acyclic Networks of Pushdown Systems
• Pumping and counting on the regular Post embedding problem
• The parametric ordinal-recursive complexity of Post embedding problems
• Zeno, Hercules, and the Hydra: safety metric temporal logic is Ackermann-complete
• On reachability for unidirectional channel systems extended with regular tests
• Multiply-recursive upper bounds with Higman's lemma
• Complexity hierarchies beyond elementary
• The ω-Regular Post Embedding Problem

This page was built for publication: Post Embedding Problem Is Not Primitive Recursive, with Applications to Channel Systems

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