On termination and invariance for faulty channel machines
From MaRDI portal
Publication:1941874
DOI10.1007/s00165-012-0234-7zbMath1259.68142MaRDI QIDQ1941874
Nicolas Markey, Philippe Schnoebelen, Patricia Bouyer, James Worrell, Joël Ouaknine
Publication date: 22 March 2013
Published in: Formal Aspects of Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00165-012-0234-7
computational complexity; metric temporal logic; primitive recursive; well-structured systems; channel machines
03B70: Logic in computer science
68Q85: Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
Zeno, Hercules, and the Hydra, Interval temporal logics over strongly discrete linear orders: expressiveness and complexity, Handling infinitely branching well-structured transition systems, On the termination and structural termination problems for counter machines with incrementing errors, Computable fixpoints in well-structured symbolic model checking, Complexity Hierarchies beyond Elementary
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Undecidable verification problems for programs with unreliable channels
- The covering and boundedness problems for vector addition systems
- Undecidable problems in unreliable computations.
- Verifying lossy channel systems has nonprimitive recursive complexity.
- Algorithmic analysis of programs with well quasi-ordered domains.
- Unreliable channels are easier to verify than perfect channels
- Safety alternating automata on data words
- Multiply-Recursive Upper Bounds with Higman’s Lemma
- Mixing Lossy and Perfect Fifo Channels
- On Communicating Finite-State Machines
- On Termination for Faulty Channel Machines
- On Computing Fixpoints in Well-Structured Regular Model Checking, with Applications to Lossy Channel Systems
- Foundations of Software Science and Computational Structures
- Ordering by Divisibility in Abstract Algebras
- Tools and Algorithms for the Construction and Analysis of Systems
- Foundations of Software Science and Computation Structures
- Well-structured transition systems everywhere!
