On the Complexity of Input Output Conformance Testing
2014 (English)In: Formal Aspects of Component Software: 10th International Symposium, FACS 2013, Nanchang, China, October 27-29, 2013, Revised Selected Papers / [ed] José Luiz Fiadeiro, Zhiming Liu & Jinyun Xue, Heidelberg: Springer, 2014, 291-309 p.Conference paper (Refereed)
Input-output conformance (ioco) testing is a well-known approach to model-based testing. In this paper, we study the complexity of checking ioco. We show that the problem of checking ioco is PSPACE-complete. To provide a more efficient algorithm, we propose a more restricted setting for checking ioco, namely with deterministic models and show that in this restricted setting ioco checking can be performed in polynomial time. © 2014 Springer International Publishing Switzerland.
Place, publisher, year, edition, pages
Heidelberg: Springer, 2014. 291-309 p.
, Lecture Notes in Computer Science, ISSN 0302-9743 ; 8348
Model-Based Testing, Conformance Testing, Complexity Theory
Computer and Information Science
IdentifiersURN: urn:nbn:se:hh:diva-24046DOI: 10.1007/978-3-319-07602-7_18ScopusID: 2-s2.0-84903554841ISBN: 978-3-319-07601-0ISBN: 978-3-319-07602-7OAI: oai:DiVA.org:hh-24046DiVA: diva2:668685
10th International Symposium on Formal Aspects of Component Software (FACS 2013), Nanchang, China, 27–29 October 2013
FundereLLIIT - The Linköping‐Lund Initiative on IT and Mobile Communications