Testing Divergent Transition Systems

Research output: Chapter in Book/Report/Conference proceedingChapter

Abstract

We revisit model-based testing for labelled transition systems in the context of specifications that may contain divergent behaviour, i.e., infinite paths of internal computations. The standard approach based on the theory of input-output conformance, known as the ioco-framework, cannot deal with divergences directly, as it restricts specifications to strongly convergent transition systems. Using the model of Quiescent Input Output Transition Systems (QIOTSs), we can handle divergence successfully in the context of quiescence. Quiescence is a fundamental notion that represents the situation that a system is not capable of producing any output, if no prior input is provided, representing lack of productive progress. The correct treatment of this situation is the cornerstone of the success of testing in the context of systems that are input-enabled, i.e., systems that accept all input actions in any state. Our revised treatment of quiescence also allows it to be preserved under determinization of a QIOTS. This last feature allows us to reformulate the standard ioco-based testing theory and algorithms in terms of classical trace-based automata theory, including finite state divergent computations.
LanguageEnglish
Title of host publicationModels, Algorithms, Logics and Tools
Subtitle of host publicationEssays Dedicated to Kim Guldstrand Larsen on the Occasion of His 60th Birthday
EditorsLuca Aceto, Giorgio Bacci, Giovanni Bacci, Anna Ingolfsdottir, Axel Legay, Radu Mardare
PublisherSpringer
Pages339
Number of pages366
ISBN (Electronic)978-3-319-63121-9
ISBN (Print)978-3-319-63120-2
DOIs
StatePublished - 25 Jul 2017
EventKimFest - Aalborg University, Aalborg, Denmark
Duration: 19 Aug 201720 Aug 2017
http://kimfest.cs.aau.dk

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume10460
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Workshop

WorkshopKimFest
Abbreviated titleKimFest
CountryDenmark
CityAalborg
Period19/08/1720/08/17
Internet address

Fingerprint

Testing
Automata theory
Specifications

Cite this

Brinksma, E., Stoelinga, M., & Timmer, M. (2017). Testing Divergent Transition Systems. In L. Aceto, G. Bacci, G. Bacci, A. Ingolfsdottir, A. Legay, & R. Mardare (Eds.), Models, Algorithms, Logics and Tools: Essays Dedicated to Kim Guldstrand Larsen on the Occasion of His 60th Birthday (pp. 339). (Lecture Notes in Computer Science; Vol. 10460). Springer. DOI: 10.1007/978-3-319-63121-9_17
Brinksma, Ed ; Stoelinga, Mariëlle ; Timmer, Mark . / Testing Divergent Transition Systems. Models, Algorithms, Logics and Tools: Essays Dedicated to Kim Guldstrand Larsen on the Occasion of His 60th Birthday. editor / Luca Aceto ; Giorgio Bacci ; Giovanni Bacci ; Anna Ingolfsdottir ; Axel Legay ; Radu Mardare. Springer, 2017. pp. 339 (Lecture Notes in Computer Science).
@inbook{125daebbd8f7410491de8099e5b33f74,
title = "Testing Divergent Transition Systems",
abstract = "We revisit model-based testing for labelled transition systems in the context of specifications that may contain divergent behaviour, i.e., infinite paths of internal computations. The standard approach based on the theory of input-output conformance, known as the ioco-framework, cannot deal with divergences directly, as it restricts specifications to strongly convergent transition systems. Using the model of Quiescent Input Output Transition Systems (QIOTSs), we can handle divergence successfully in the context of quiescence. Quiescence is a fundamental notion that represents the situation that a system is not capable of producing any output, if no prior input is provided, representing lack of productive progress. The correct treatment of this situation is the cornerstone of the success of testing in the context of systems that are input-enabled, i.e., systems that accept all input actions in any state. Our revised treatment of quiescence also allows it to be preserved under determinization of a QIOTS. This last feature allows us to reformulate the standard ioco-based testing theory and algorithms in terms of classical trace-based automata theory, including finite state divergent computations.",
author = "Ed Brinksma and Mari{\"e}lle Stoelinga and Mark Timmer",
year = "2017",
month = "7",
day = "25",
doi = "10.1007/978-3-319-63121-9_17",
language = "English",
isbn = "978-3-319-63120-2",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "339",
editor = "Luca Aceto and Giorgio Bacci and Giovanni Bacci and Anna Ingolfsdottir and Axel Legay and Radu Mardare",
booktitle = "Models, Algorithms, Logics and Tools",

}

Brinksma, E, Stoelinga, M & Timmer, M 2017, Testing Divergent Transition Systems. in L Aceto, G Bacci, G Bacci, A Ingolfsdottir, A Legay & R Mardare (eds), Models, Algorithms, Logics and Tools: Essays Dedicated to Kim Guldstrand Larsen on the Occasion of His 60th Birthday. Lecture Notes in Computer Science, vol. 10460, Springer, pp. 339, KimFest, Aalborg, Denmark, 19/08/17. DOI: 10.1007/978-3-319-63121-9_17

Testing Divergent Transition Systems. / Brinksma, Ed; Stoelinga, Mariëlle; Timmer, Mark .

Models, Algorithms, Logics and Tools: Essays Dedicated to Kim Guldstrand Larsen on the Occasion of His 60th Birthday. ed. / Luca Aceto; Giorgio Bacci; Giovanni Bacci; Anna Ingolfsdottir; Axel Legay; Radu Mardare. Springer, 2017. p. 339 (Lecture Notes in Computer Science; Vol. 10460).

Research output: Chapter in Book/Report/Conference proceedingChapter

TY - CHAP

T1 - Testing Divergent Transition Systems

AU - Brinksma,Ed

AU - Stoelinga,Mariëlle

AU - Timmer,Mark

PY - 2017/7/25

Y1 - 2017/7/25

N2 - We revisit model-based testing for labelled transition systems in the context of specifications that may contain divergent behaviour, i.e., infinite paths of internal computations. The standard approach based on the theory of input-output conformance, known as the ioco-framework, cannot deal with divergences directly, as it restricts specifications to strongly convergent transition systems. Using the model of Quiescent Input Output Transition Systems (QIOTSs), we can handle divergence successfully in the context of quiescence. Quiescence is a fundamental notion that represents the situation that a system is not capable of producing any output, if no prior input is provided, representing lack of productive progress. The correct treatment of this situation is the cornerstone of the success of testing in the context of systems that are input-enabled, i.e., systems that accept all input actions in any state. Our revised treatment of quiescence also allows it to be preserved under determinization of a QIOTS. This last feature allows us to reformulate the standard ioco-based testing theory and algorithms in terms of classical trace-based automata theory, including finite state divergent computations.

AB - We revisit model-based testing for labelled transition systems in the context of specifications that may contain divergent behaviour, i.e., infinite paths of internal computations. The standard approach based on the theory of input-output conformance, known as the ioco-framework, cannot deal with divergences directly, as it restricts specifications to strongly convergent transition systems. Using the model of Quiescent Input Output Transition Systems (QIOTSs), we can handle divergence successfully in the context of quiescence. Quiescence is a fundamental notion that represents the situation that a system is not capable of producing any output, if no prior input is provided, representing lack of productive progress. The correct treatment of this situation is the cornerstone of the success of testing in the context of systems that are input-enabled, i.e., systems that accept all input actions in any state. Our revised treatment of quiescence also allows it to be preserved under determinization of a QIOTS. This last feature allows us to reformulate the standard ioco-based testing theory and algorithms in terms of classical trace-based automata theory, including finite state divergent computations.

U2 - 10.1007/978-3-319-63121-9_17

DO - 10.1007/978-3-319-63121-9_17

M3 - Chapter

SN - 978-3-319-63120-2

T3 - Lecture Notes in Computer Science

SP - 339

BT - Models, Algorithms, Logics and Tools

PB - Springer

ER -

Brinksma E, Stoelinga M, Timmer M. Testing Divergent Transition Systems. In Aceto L, Bacci G, Bacci G, Ingolfsdottir A, Legay A, Mardare R, editors, Models, Algorithms, Logics and Tools: Essays Dedicated to Kim Guldstrand Larsen on the Occasion of His 60th Birthday. Springer. 2017. p. 339. (Lecture Notes in Computer Science). Available from, DOI: 10.1007/978-3-319-63121-9_17