On the complexity of verifying concurrent transition systems

DOI10.1006/INCO.2001.2920MaRDI QIDQ1854510zbMATH OpenOpenAlexFDO

Authors David Harel, Orna Kupferman, Moshe Y. Vardi

Publication date 14 January 2003

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/inco.2001.2920

Mathematics Subject Classification ID

Specification and verification (program logics, model checking, etc.) (68Q60) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Recommendations

• On the complexity of verifying concurrent transition systems
• scientific article; zbMATH DE number 1332671
• Automatic verification of finite-state concurrent systems using temporal logic specifications
• Distributed Computing
• The complexity of probabilistic verification

Cites work

• scientific article; zbMATH DE number 3903948 (Why is no real title available?)
• scientific article; zbMATH DE number 3735115 (Why is no real title available?)
• scientific article; zbMATH DE number 42752 (Why is no real title available?)
• scientific article; zbMATH DE number 52331 (Why is no real title available?)
• scientific article; zbMATH DE number 1332671 (Why is no real title available?)
• scientific article; zbMATH DE number 734956 (Why is no real title available?)
• scientific article; zbMATH DE number 2102770 (Why is no real title available?)
• A calculus of communicating systems
• Alternation
• An automata-theoretic approach to branching-time model checking
• Complexity of equivalence problems for concurrent systems of finite agents
• Deciding bisimilarity is P-complete
• On the power of bounded concurrency I
• On the power of bounded concurrency II
• Protocol Verification via Projections
• Reasoning about infinite computations
• Statecharts: a visual formalism for complex systems
• The complementation problem for Büchi automata with applications to temporal logic
• The existence of refinement mappings

Cited in

(24)

• A Rice-style theorem for parallel automata
• Predecessor existence problems for finite discrete dynamical systems
• Formalization and correctness of a concurrent linear hash structure algorithm using nested transactions and I/O automata
• Under-approximation of reachability in multivalued asynchronous networks
• The Complexity of Reliable Concurrency Control
• The computational complexity of scenario-based agent verification and design
• On the Complexity of Verifying Regular Properties on Flat Counter Systems,
• A parametric analysis of the state-explosion problem in model checking
• On the Complexity of Bounded Context Switching.
• On the complexity of verifying concurrent transition systems
• Proceedings of the workshop on graph transformation for concurrency and verification (GT-VC 2006), Bonn, Germany, August 31, 2006
• Checking simple properties of transition systems defined by Thue specifications
• A consistency analysis of a class of concurrent transient implicit/explicit algorithms
• Sufficient conditions for reachability in automata networks with priorities
• Decidability and complexity for quiescent consistency and its variations
• Modeling and analyzing social network dynamics using stochastic discrete graphical dynamical systems
• Complexity of reachability problems for finite discrete dynamical systems
• Efficient verification of concurrent systems using local-analysis-based approximations and SAT solving
• Distributed Computing
• scientific article; zbMATH DE number 7167584 (Why is no real title available?)
• Reachability problems for sequential dynamical systems with threshold functions.
• A Parametrized Analysis of Algorithms on Hierarchical Graphs
• Tools and Algorithms for the Construction and Analysis of Systems
• PSPACE-completeness of modular supervisory control problems

This page was built for publication: On the complexity of verifying concurrent transition systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1854510)