Complexity of Decision Problems for Mixed and Modal Specifications

Adam Antonik, Michael Huth, Ulrik Mathias Nyman, Kim Guldstrand Larsen, Andrzej Wasowski

    Research output: Journal Article or Conference Article in JournalConference articleResearchpeer-review

    Abstract

    We consider decision problems for modal and mixed transition systems used as specifications: the common implementation problem (whether a set of specifications has a common implementation), the consistency problem (whether a single specification has an implementation), and the thorough refinement problem (whether all implementations of one specification are also implementations of another one). Common implementation and thorough refinement are shown to be PSPACE-hard for modal, and so also for mixed, specifications. Consistency is PSPACE-hard
    for mixed, while trivial for modal specifications. We also supply upper bounds suggesting strong links between these problems.

    Original languageEnglish
    Book seriesLecture Notes in Computer Science
    Pages (from-to)112-126
    ISSN0302-9743
    DOIs
    Publication statusPublished - 2008
    Event11th International Conference, FOSSACS 2008:Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2008, Budapest, Hungary, March 29 - April 6, 2008. - Budapest, Hungary
    Duration: 29 Mar 20086 Apr 2008
    Conference number: 11

    Conference

    Conference11th International Conference, FOSSACS 2008:Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2008, Budapest, Hungary, March 29 - April 6, 2008.
    Number11
    Country/TerritoryHungary
    CityBudapest
    Period29/03/200806/04/2008

    Keywords

    • Modal Specifications
    • Mixed Transition Systems
    • Common Implementation
    • Thorough Refinement
    • Consistency Problem

    Cite this