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

DOI10.1007/978-3-540-77050-3_22zbMATH Open1136.03030OpenAlexW1528258327WikidataQ56095061 ScholiaQ56095061MaRDI QIDQ5458840FDOQ5458840

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

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

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)

Cites Work

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

Cited In (9)

• 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
• Mixing Lossy and Perfect Fifo Channels

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)