EXPTIME-complete decision problems for modal and mixed specifications

DOI10.1016/J.ENTCS.2009.06.011MaRDI QIDQ5170664zbMATH OpenOpenAlexFDO

Authors Adam Antonik, Michael Huth, Ulrik Nyman, Andrzej Wąsowski, Kim G. 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

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Specification and verification (program logics, model checking, etc.) (68Q60) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Recommendations

• Modal and mixed specifications: key decision problems and their complexities
• Complexity of Decision Problems for Mixed and Modal Specifications
• EXPTIME-completeness of thorough refinement on modal transition systems
• Checking Thorough Refinement on Modal Transition Systems Is EXPTIME-Complete
• On Modal Refinement and Consistency

Cites work

• scientific article; zbMATH DE number 3716792 (Why is no real title available?)
• scientific article; zbMATH DE number 1953032 (Why is no real title available?)
• scientific article; zbMATH DE number 1759610 (Why is no real title available?)
• scientific article; zbMATH DE number 898449 (Why is no real title available?)
• 20 years of modal and mixed specifications.
• Alternation
• Automata games for multiple-model checking
• Automatic verification methods for finite state systems. International workshop, Grenoble, France, June 12-14, 1989. Proceedings
• Comparing disjunctive modal transition systems with an one-selecting variant
• Complexity of Decision Problems for Mixed and Modal Specifications
• Labelled transition systems as a Stone space
• Modal I/O Automata for Interface and Product Line Theories
• On Modal Refinement and Consistency
• On model checking multiple hybrid views
• On the complexity of semantic self-minimization
• State explosion in almost-sure probabilistic reachability

Cited in

(6)

• 20 years of modal and mixed specifications.
• Modal and mixed specifications: key decision problems and their complexities
• Complexity of Decision Problems for Mixed and Modal Specifications
• On the consistency, expressiveness, and precision of partial modeling formalisms
• EXPTIME-completeness of thorough refinement on modal transition systems
• Simulation relations and applications in formal methods

This page was built for publication: EXPTIME-complete decision problems for modal and mixed specifications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5170664)