EXPTIME-completeness of thorough refinement on modal transition systems

DOI10.1016/J.IC.2012.08.001MaRDI QIDQ690504zbMATH OpenOpenAlexFDO

Authors Nikola Beneš, Jan Křetínský, Jiří Srba, Kim G. Larsen

Publication date 27 November 2012

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ic.2012.08.001

zbMATH Keywords

computational complexityrefinementmodal transition systems

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)

Recommendations

• Checking Thorough Refinement on Modal Transition Systems Is EXPTIME-Complete
• EXPTIME-complete decision problems for modal and mixed specifications
• On refinements of Boolean and parametric modal transition systems
• scientific article; zbMATH DE number 2015290
• Refinement checking on parametric modal transition systems
• Analyzing completeness of axiomatic functional systems for temporal \(\times \) modal logics
• Expressive completeness through logically tractable models
• Modal transition systems: composition and LTL model checking
• Adequacy and complete axiomatization for timed modal logic
• scientific article; zbMATH DE number 1499093

Cites work

• scientific article; zbMATH DE number 1693039 (Why is no real title available?)
• scientific article; zbMATH DE number 5595162 (Why is no real title available?)
• scientific article; zbMATH DE number 1863177 (Why is no real title available?)
• 20 years of modal and mixed specifications.
• Behavioural equivalences on finite-state systems are PTIME-hard
• CCS expressions, finite state processes, and three problems of equivalence
• Comparing disjunctive modal transition systems with an one-selecting variant
• Complexity of Decision Problems for Mixed and Modal Specifications
• Compositional verification and 3-valued abstractions join forces
• Deciding bisimilarity is P-complete
• Mixed Transition Systems Revisited
• Modal Abstractions of Concurrent Behaviour
• Modal and mixed specifications: key decision problems and their complexities
• On Modal Refinement and Consistency
• On determinism in modal transition systems
• On weak modal compatibility, refinement, and the MIO workbench
• Refinement and Consistency of Timed Modal Specifications
• Three Partition Refinement Algorithms

Cited in

(5)

• Refinement checking on parametric modal transition systems
• EXPTIME-complete decision problems for modal and mixed specifications
• Coherent modal transition systems refinement
• Checking Thorough Refinement on Modal Transition Systems Is EXPTIME-Complete
• On refinements of Boolean and parametric modal transition systems

Describes a project that uses

Uses Software

• MIO Workbench
• MTSA

This page was built for publication: EXPTIME-completeness of thorough refinement on modal transition systems

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