On refinements of boolean and parametric modal transition systems

Jan Křetínský; Salomon Sickert

doi:10.1007/978-3-642-39718-9_13

On refinements of boolean and parametric modal transition systems

Jan Křetínský, Salomon Sickert

Informatics 7 - Associate Professorship of Formal Methods for Software Reliability

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

5 Scopus citations

Abstract

We consider the extensions of modal transition systems (MTS), namely Boolean MTS and parametric MTS and we investigate the refinement problems over both classes. Firstly, we reduce the problem of modal refinement over both classes to a problem solvable by a QBF solver and provide experimental results showing our technique scales well. Secondly, we extend the algorithm for thorough refinement of MTS providing better complexity than via reductions to previously studied problems. Finally, we investigate the relationship between modal and thorough refinement on the two classes and show how the thorough refinement can be approximated by the modal refinement.

Original language	English
Title of host publication	Theoretical Aspects of Computing, ICTAC 2013 - 10th International Colloquium, Proceedings
Publisher	Springer Verlag
Pages	213-230
Number of pages	18
ISBN (Print)	9783642397172
DOIs	https://doi.org/10.1007/978-3-642-39718-9_13
State	Published - 2013
Event	10th International Colloquium on Theoretical Aspects of Computing, ICTAC 2013 - Shanghai, China Duration: 4 Sep 2013 → 6 Sep 2013

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	8049 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	10th International Colloquium on Theoretical Aspects of Computing, ICTAC 2013
Country/Territory	China
City	Shanghai
Period	4/09/13 → 6/09/13

Access to Document

10.1007/978-3-642-39718-9_13

Cite this

Křetínský, J., & Sickert, S. (2013). On refinements of boolean and parametric modal transition systems. In Theoretical Aspects of Computing, ICTAC 2013 - 10th International Colloquium, Proceedings (pp. 213-230). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8049 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-642-39718-9_13

@inproceedings{de4ea850983c48599396e0d31d7b13a2,

title = "On refinements of boolean and parametric modal transition systems",

abstract = "We consider the extensions of modal transition systems (MTS), namely Boolean MTS and parametric MTS and we investigate the refinement problems over both classes. Firstly, we reduce the problem of modal refinement over both classes to a problem solvable by a QBF solver and provide experimental results showing our technique scales well. Secondly, we extend the algorithm for thorough refinement of MTS providing better complexity than via reductions to previously studied problems. Finally, we investigate the relationship between modal and thorough refinement on the two classes and show how the thorough refinement can be approximated by the modal refinement.",

author = "Jan K{\v r}et{\'i}nsk{\'y} and Salomon Sickert",

year = "2013",

doi = "10.1007/978-3-642-39718-9_13",

language = "English",

isbn = "9783642397172",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "213--230",

booktitle = "Theoretical Aspects of Computing, ICTAC 2013 - 10th International Colloquium, Proceedings",

note = "10th International Colloquium on Theoretical Aspects of Computing, ICTAC 2013 ; Conference date: 04-09-2013 Through 06-09-2013",

}

Křetínský, J & Sickert, S 2013, On refinements of boolean and parametric modal transition systems. in Theoretical Aspects of Computing, ICTAC 2013 - 10th International Colloquium, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8049 LNCS, Springer Verlag, pp. 213-230, 10th International Colloquium on Theoretical Aspects of Computing, ICTAC 2013, Shanghai, China, 4/09/13. https://doi.org/10.1007/978-3-642-39718-9_13

On refinements of boolean and parametric modal transition systems. / Křetínský, Jan; Sickert, Salomon.
Theoretical Aspects of Computing, ICTAC 2013 - 10th International Colloquium, Proceedings. Springer Verlag, 2013. p. 213-230 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8049 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - On refinements of boolean and parametric modal transition systems

AU - Křetínský, Jan

AU - Sickert, Salomon

PY - 2013

Y1 - 2013

N2 - We consider the extensions of modal transition systems (MTS), namely Boolean MTS and parametric MTS and we investigate the refinement problems over both classes. Firstly, we reduce the problem of modal refinement over both classes to a problem solvable by a QBF solver and provide experimental results showing our technique scales well. Secondly, we extend the algorithm for thorough refinement of MTS providing better complexity than via reductions to previously studied problems. Finally, we investigate the relationship between modal and thorough refinement on the two classes and show how the thorough refinement can be approximated by the modal refinement.

AB - We consider the extensions of modal transition systems (MTS), namely Boolean MTS and parametric MTS and we investigate the refinement problems over both classes. Firstly, we reduce the problem of modal refinement over both classes to a problem solvable by a QBF solver and provide experimental results showing our technique scales well. Secondly, we extend the algorithm for thorough refinement of MTS providing better complexity than via reductions to previously studied problems. Finally, we investigate the relationship between modal and thorough refinement on the two classes and show how the thorough refinement can be approximated by the modal refinement.

UR - http://www.scopus.com/inward/record.url?scp=84885007702&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-39718-9_13

DO - 10.1007/978-3-642-39718-9_13

M3 - Conference contribution

AN - SCOPUS:84885007702

SN - 9783642397172

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 213

EP - 230

BT - Theoretical Aspects of Computing, ICTAC 2013 - 10th International Colloquium, Proceedings

PB - Springer Verlag

T2 - 10th International Colloquium on Theoretical Aspects of Computing, ICTAC 2013

Y2 - 4 September 2013 through 6 September 2013

ER -

Křetínský J, Sickert S. On refinements of boolean and parametric modal transition systems. In Theoretical Aspects of Computing, ICTAC 2013 - 10th International Colloquium, Proceedings. Springer Verlag. 2013. p. 213-230. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-39718-9_13

On refinements of boolean and parametric modal transition systems

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this