EXPTIME-complete Decision Problems for Modal and Mixed Specifications

DOI10.1016/j.entcs.2009.06.011zbMath1291.68172OpenAlexW2120514221MaRDI QIDQ5170664

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

Publication date: 23 July 2014

Published in: Electronic Notes in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.entcs.2009.06.011

zbMATH Keywords

decision problemEXPTIME-completenessmodal transition systemmixed transition system

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

Related Items (3)

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• State explosion in almost-sure probabilistic reachability
• On model checking multiple hybrid views
• Comparing disjunctive modal transition systems with an one-selecting variant
• Automatic verification methods for finite state systems. International workshop, Grenoble, France, June 12-14, 1989. Proceedings
• On the Complexity of Semantic Self-minimization
• On Modal Refinement and Consistency
• Alternation
• Labelled transition systems as a Stone space
• Complexity of Decision Problems for Mixed and Modal Specifications
• Modal I/O Automata for Interface and Product Line Theories

This page was built for publication: EXPTIME-complete Decision Problems for Modal and Mixed Specifications