The ω-Regular Post Embedding Problem
DOI10.1007/978-3-540-78499-9_8zbMATH Open1139.03031OpenAlexW100843780MaRDI QIDQ5458353FDOQ5458353
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
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 \(\omega\)-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
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
- Foundations of Software Science and Computation Structures
- 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
- Undecidable verification problems for programs with unreliable channels
- Title not available (Why is that?)
- Nets with Tokens Which Carry Data
- Constraint-based automatic verification of abstract models of multithreaded programs
- Non-primitive recursive decidability of products of modal logics with expanding domains
- Automated Deduction – CADE-20
- Une généralisation des théorèmes de Higman et de Simon aux mots infinis
- On Computing Fixpoints in Well-Structured Regular Model Checking, with Applications to Lossy Channel Systems
- Foundations of Software Science and Computational Structures
- Automata, Languages and Programming
- Post Embedding Problem Is Not Primitive Recursive, with Applications to Channel Systems
Cited In (6)
- 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
- Mixing Lossy and Perfect Fifo Channels
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)
