Complexity of Decision Problems for Mixed and Modal Specifications

DOI10.1007/978-3-540-78499-9_9zbMath1139.68035OpenAlexW1608677350MaRDI QIDQ5458354

Andrzej Wąsowski, Adam Antonik, Ulrik Nyman, Michael Huth, Kim Guldstrand Larsen

Publication date: 11 April 2008

Published in: Foundations of Software Science and Computational Structures (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-78499-9_9

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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (7)

On the consistency, expressiveness, and precision of partial modeling formalisms ⋮ Simulation relations and applications in formal methods ⋮ Modal and mixed specifications: key decision problems and their complexities ⋮ EXPTIME-completeness of thorough refinement on modal transition systems ⋮ EXPTIME-complete Decision Problems for Modal and Mixed Specifications ⋮ On the Complexity of Semantic Self-minimization ⋮ Refinement checking on parametric modal transition systems

Cites Work

• Comparing disjunctive modal transition systems with an one-selecting variant
• Model checking hybrid logics (with an application to semistructured data)
• On Modal Refinement and Consistency
• Labelled transition systems as a Stone space
• Alternating tree automata, parity games, and modal \(\mu\)-calculus
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Complexity of Decision Problems for Mixed and Modal Specifications