Vi ser på beslutsproblem för system för modal och blandad övergång som används som specifikationer: det gemensamma genomförandeproblemet (om en uppsättning specifikationer har ett gemensamt genomförande), konsekvensproblemet (om en enda specifikation har ett genomförande) och det grundläggande förbättringsproblemet (om alla genomföranden av en specifikation också är genomförande av en annan). Gemensamt genomförande och grundlig förfining visas vara PSPACE-hård för modal, och så även för blandade, specifikationer. Överensstämmelse är PSPACEhard för blandade, medan trivialt för modal specifikationer. Vi tillhandahåller också övre gränser som tyder på starka kopplingar mellan dessa problem.
Konferensdokumentet REF ) visar också att TR för modal specifikationer är PSPACE-hård.
Complexity of Decision Problems for Mixed and Modal Specifications ⋆
{'venue': 'FoSSaCS', 'journal': None, 'mag_field_of_study': ['Computer Science']}