EXPTIME-completeness of thorough refinement on modal transition systems

DOI10.1016/j.ic.2012.08.001zbMath1282.68118OpenAlexW2021472259MaRDI QIDQ690504

Nikola Beneš, Jiří Srba, Jan Křetínský, Kim Guldstrand Larsen

Publication date: 27 November 2012

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

Full work available at URL: https://doi.org/10.1016/j.ic.2012.08.001

zbMATH Keywords

computational complexityrefinementmodal transition systems

Mathematics Subject Classification ID

Specification and verification (program logics, model checking, etc.) (68Q60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Coherent modal transition systems refinement ⋮ Refinement checking on parametric modal transition systems

Uses Software

• MIO Workbench
• MSTA

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On determinism in modal transition systems
• CCS expressions, finite state processes, and three problems of equivalence
• Comparing disjunctive modal transition systems with an one-selecting variant
• Deciding bisimilarity is P-complete
• Compositional verification and 3-valued abstractions join forces
• Modal Abstractions of Concurrent Behaviour
• On Modal Refinement and Consistency
• Modal and mixed specifications: key decision problems and their complexities
• On Weak Modal Compatibility, Refinement, and the MIO Workbench
• Mixed Transition Systems Revisited
• Refinement and Consistency of Timed Modal Specifications
• Three Partition Refinement Algorithms
• Complexity of Decision Problems for Mixed and Modal Specifications