On termination and invariance for faulty channel machines

DOI10.1007/s00165-012-0234-7zbMath1259.68142OpenAlexW2083176536MaRDI 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 complexitymetric temporal logicprimitive recursivewell-structured systemschannel machines

Mathematics Subject Classification ID

Logic in computer science (03B70) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (6)

Zeno, Hercules, and the Hydra ⋮ Handling infinitely branching well-structured transition systems ⋮ Interval temporal logics over strongly discrete linear orders: expressiveness and complexity ⋮ Computable fixpoints in well-structured symbolic model checking ⋮ On the termination and structural termination problems for counter machines with incrementing errors ⋮ 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!

This page was built for publication: On termination and invariance for faulty channel machines