On the complexity of verifying concurrent transition systems

DOI10.1007/3-540-63141-0_18zbMath1512.68155OpenAlexW1604214744MaRDI QIDQ6044122

Moshe Y. Vardi, Orna Kupferman, David Harel

Publication date: 17 May 2023

Published in: CONCUR '97: Concurrency Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-63141-0_18

Mathematics Subject Classification ID

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

Related Items

Hardness of preorder checking for basic formalisms, Alternation and bounded concurrency are reverse equivalent., Is your model checker on time? On the complexity of model checking for timed modal logics

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The existence of refinement mappings
• The complementation problem for Büchi automata with applications to temporal logic
• Statecharts: a visual formalism for complex systems
• A calculus of communicating systems
• Deciding bisimilarity is P-complete
• Reasoning about infinite computations
• Protocol Verification via Projections
• Alternation
• On the power of bounded concurrency I
• On the power of bounded concurrency II
• Equivalences for fair Kripke structures