Complexity of Decision Problems for Mixed and Modal Specifications

DOI10.1007/978-3-540-78499-9_9zbMath1139.68035MaRDI 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

68Q25: Analysis of algorithms and problem complexity

68Q60: Specification and verification (program logics, model checking, etc.)

68Q85: Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Related Items

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

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