The ω-Regular Post Embedding Problem

DOI10.1007/978-3-540-78499-9_8MaRDI QIDQ5458353zbMATH OpenOpenAlexFDO

Authors Pierre Chambart, Philippe Schnoebelen

Publication date 11 April 2008

Published in Foundations of Software Science and Computational Structures (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-78499-9_8

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 parametric ordinal-recursive complexity of Post embedding problems
• Pumping and counting on the regular Post embedding problem
• scientific article; zbMATH DE number 3918757
• Embedding -continuous posets in function spaces of domains
• Connes' embedding problem and Tsirelson's problem
• scientific article; zbMATH DE number 1166352
• scientific article; zbMATH DE number 3939344
• The embedding problem in iteration theory
• scientific article; zbMATH DE number 2079047

Cites work

• scientific article; zbMATH DE number 1809622 (Why is no real title available?)
• Automata, Languages and Programming
• Automated Deduction – CADE-20
• Constraint-based automatic verification of abstract models of multithreaded programs
• Foundations of Software Science and Computation Structures
• Foundations of Software Science and Computational Structures
• Nets with Tokens Which Carry Data
• Non-primitive recursive decidability of products of modal logics with expanding domains
• On Computing Fixpoints in Well-Structured Regular Model Checking, with Applications to Lossy Channel Systems
• On the decidability and complexity of Metric Temporal Logic over finite words
• Post Embedding Problem Is Not Primitive Recursive, with Applications to Channel Systems
• Undecidable verification problems for programs with unreliable channels
• Une généralisation des théorèmes de Higman et de Simon aux mots infinis
• Verifying lossy channel systems has nonprimitive recursive complexity.
• Verifying programs with unreliable channels

Cited in

(6)

• Mixing Lossy and Perfect Fifo Channels
• Pumping and counting on the regular Post embedding problem
• The parametric ordinal-recursive complexity of Post embedding problems
• Regular embeddings of the stationary tower and Woodin's maximality theorem
• Post Embedding Problem Is Not Primitive Recursive, with Applications to Channel Systems
• Complexity hierarchies beyond elementary

This page was built for publication: The ω-Regular Post Embedding Problem

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