On termination and invariance for faulty channel machines

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

zbMATH Keywords

computational complexity; metric temporal logic; primitive recursive; well-structured systems; channel machines

Mathematics Subject Classification ID

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!