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

Higman's LemmaLossy channel systemsPost correspondence problem

Mathematics Subject Classification ID

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

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

• Alternating timed automata
• Automated Deduction – CADE-20
• Bisimulation and other undecidable equivalences for lossy channel systems
• Decidability and complexity results for timed automata via channel machines
• scientific article; zbMATH DE number 1809622 (Why is no real title available?)
• 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

(10)

• Complexity hierarchies beyond elementary
• Multiply-recursive upper bounds with Higman's lemma
• 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
• On reachability for unidirectional channel systems extended with regular tests
• Zeno, Hercules, and the Hydra: safety metric temporal logic is Ackermann-complete
• The ω-Regular Post Embedding Problem
• Tight length theorems for multiset extensions of Higman's lemma

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)