The ω-Regular Post Embedding Problem

DOI10.1007/978-3-540-78499-9_8zbMath1139.03031MaRDI QIDQ5458353

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

03D05: Automata and formal grammars in connection with logical questions

68Q85: Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)

03B25: Decidability of theories and sets of sentences

03D40: Word problems, etc. in computability and recursion theory

03D03: Thue and Post systems, etc.

Related Items

Generalized Post embedding problems, Complexity Hierarchies beyond Elementary, Mixing Lossy and Perfect Fifo Channels

Cites Work

• Unnamed Item
• 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
• Non-primitive recursive decidability of products of modal logics with expanding domains
• Constraint-based automatic verification of abstract models of multithreaded programs
• Nets with Tokens Which Carry Data
• On the decidability and complexity of Metric Temporal Logic over finite words
• On Computing Fixpoints in Well-Structured Regular Model Checking, with Applications to Lossy Channel Systems
• Automated Deduction – CADE-20
• Post Embedding Problem Is Not Primitive Recursive, with Applications to Channel Systems
• Foundations of Software Science and Computational Structures
• Automata, Languages and Programming
• Foundations of Software Science and Computation Structures