Complexity of Decision Problems for Mixed and Modal Specifications

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

doi:10.1007/978-3-540-78499-9

Complexity of Decision Problems for Mixed and Modal Specifications

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

Publikation: Artikel i tidsskrift og konference artikel i tidsskrift › Konferenceartikel › Forskning › peer 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.

Originalsprog	Engelsk
Bogserie	Lecture Notes in Computer Science
Sider (fra-til)	112-126
ISSN	0302-9743
DOI	https://doi.org/10.1007/978-3-540-78499-9
Status	Udgivet - 2008
Begivenhed	11th 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, Ungarn Varighed: 29 mar. 2008 → 6 apr. 2008 Konferencens nummer: 11

Konference

Konference	11th 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.
Nummer	11
Land/Område	Ungarn
By	Budapest
Periode	29/03/2008 → 06/04/2008

Emneord

Modal Specifications
Mixed Transition Systems
Common Implementation
Thorough Refinement
Consistency Problem

Adgang til dokumentet

10.1007/978-3-540-78499-9

Citationsformater

@inproceedings{26ebc910946411dd8006000ea68e967b,

title = "Complexity of Decision Problems for Mixed and Modal Specifications",

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-hardfor mixed, while trivial for modal specifications. We also supply upper bounds suggesting strong links between these problems.",

keywords = "Modal Specifications, Mixed Transition Systems, Common Implementation, Thorough Refinement, Consistency Problem, Modal Specifications, Mixed Transition Systems, Common Implementation, Thorough Refinement, Consistency Problem",

author = "Adam Antonik and Michael Huth and Nyman, {Ulrik Mathias} and Larsen, {Kim Guldstrand} and Andrzej Wasowski",

note = "Serie: Lecture Notes in Computer Science, Springer, 4962, 0302-9743, 1611-3349; 11th 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. ; Conference date: 29-03-2008 Through 06-04-2008",

year = "2008",

doi = "10.1007/978-3-540-78499-9",

language = "English",

pages = "112--126",

journal = "Lecture Notes in Computer Science",

issn = "0302-9743",

publisher = "Springer",

}

TY - GEN

T1 - Complexity of Decision Problems for Mixed and Modal Specifications

AU - Antonik, Adam

AU - Huth, Michael

AU - Nyman, Ulrik Mathias

AU - Larsen, Kim Guldstrand

AU - Wasowski, Andrzej

N1 - Conference code: 11

PY - 2008

Y1 - 2008

N2 - 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-hardfor mixed, while trivial for modal specifications. We also supply upper bounds suggesting strong links between these problems.

AB - 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-hardfor mixed, while trivial for modal specifications. We also supply upper bounds suggesting strong links between these problems.

KW - Modal Specifications

KW - Mixed Transition Systems

KW - Common Implementation

KW - Thorough Refinement

KW - Consistency Problem

KW - Modal Specifications

KW - Mixed Transition Systems

KW - Common Implementation

KW - Thorough Refinement

KW - Consistency Problem

U2 - 10.1007/978-3-540-78499-9

DO - 10.1007/978-3-540-78499-9

M3 - Conference article

SN - 0302-9743

SP - 112

EP - 126

JO - Lecture Notes in Computer Science

JF - Lecture Notes in Computer Science

T2 - 11th 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.

Y2 - 29 March 2008 through 6 April 2008

ER -