Divergent Quiescent Transition Systems (extended version)

Willem G.J. Stokkink, Mark Timmer, Mariëlle I.A. Stoelinga

    Research output: Book/ReportReportAcademic

    30 Downloads (Pure)


    Quiescence is a fundamental concept in modelling system behaviour, as it explicitly represents the fact that no output is produced in certain states. The notion of quiescence is also essential to model-based testing: if a particular implementation under test does not provide any output, then the test evaluation algorithm must decide whether or not to allow this behaviour. To explicitly model quiescence in all its glory, we introduce Divergent Quiescent Transition Systems (DQTSs). DQTSs model quiescence using explicit delta-labelled transitions, analogous to Suspension Automata (SAs) in the well-known ioco framework. Whereas SAs have only been defined implicitly, DQTSs for the first time provide a fully-formalised framework for quiescence. Also, while SAs are restricted to convergent systems (i.e., without tau-cycles), we show how quiescence can be treated naturally using a notion of fairness, allowing systems exhibiting divergence to be modelled as well. We study compositionality under the familiar automata-theoretical operations of determinisation, parallel composition and action hiding. We provide a non-trivial algorithm for detecting divergent states, and discuss its complexity. Finally, we show how to use DQTSs in the context of model-based testing, for the first time presenting a full-fledged theory that allows ioco to be applied to divergent systems.
    Original languageEnglish
    Place of PublicationEnschede
    PublisherCentre for Telematics and Information Technology (CTIT)
    Number of pages39
    Publication statusPublished - Mar 2013

    Publication series

    NameCTIT Technical Report Series
    PublisherUniversity of Twente, Centre for Telematica and Information Technology (CTIT)
    ISSN (Print)1381-3625


    • EC Grant Agreement nr.: FP7/2007-2013
    • EC Grant Agreement nr.: FP7/318490


    Dive into the research topics of 'Divergent Quiescent Transition Systems (extended version)'. Together they form a unique fingerprint.

    Cite this