The ω-Regular Post Embedding Problem

DOI10.1007/978-3-540-78499-9_8zbMath1139.03031OpenAlexW100843780MaRDI 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

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

Related Items (3)

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

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

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