Modal and mixed specifications: key decision problems and their complexities

DOI10.1017/S0960129509990260MaRDI QIDQ3550702zbMATH OpenOpenAlexFDO

Authors Adam Antonik, Michael Huth, Ulrik Nyman, Andrzej Wąsowski, Kim G. Larsen

Publication date 1 April 2010

Published in Mathematical Structures in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1017/s0960129509990260

zbMATH Keywords

transition systems

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)

Recommendations

• Complexity of Decision Problems for Mixed and Modal Specifications
• EXPTIME-complete decision problems for modal and mixed specifications
• 20 years of modal and mixed specifications.
• On Modal Refinement and Consistency
• Checking Thorough Refinement on Modal Transition Systems Is EXPTIME-Complete

Cites work

• scientific article; zbMATH DE number 5595151 (Why is no real title available?)
• A finite model theorem for the propositional \(\mu\)-calculus
• Alternation
• Checking Thorough Refinement on Modal Transition Systems Is EXPTIME-Complete
• Complexity of Decision Problems for Mixed and Modal Specifications
• EXPTIME-complete decision problems for modal and mixed specifications
• Infinite games on finitely coloured graphs with applications to automata on infinite trees
• Labelled transition systems as a Stone space
• On the complexity of semantic self-minimization
• Refinement is complete for implementations
• State explosion in almost-sure probabilistic reachability
• Strategy Construction for Parity Games with Imperfect Information
• Three theorems on phrase structure grammars of type 1

Cited in

(5)

• 20 years of modal and mixed specifications.
• Complexity of Decision Problems for Mixed and Modal Specifications
• EXPTIME-complete decision problems for modal and mixed specifications
• Consistency and refinement for interval Markov chains
• EXPTIME-completeness of thorough refinement on modal transition systems

This page was built for publication: Modal and mixed specifications: key decision problems and their complexities

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