King's College London

Research portal

Testing conformance of a deterministic implementation against a non-deterministic stream X-machine

Research output: Contribution to journalArticle

Robert Mark Hierons, Mark Harman

Original languageEnglish
Pages (from-to)191-233
Number of pages43
JournalJournal of Theoretical Computer Science
Issue number1-3
Published14 Sep 2004

King's Authors


Stream X-machines are a formalisation of extended finite state machines that have been used to specify systems. One of the great benefits of using stream X-machines, for the purpose of specification, is the associated test generation technique which produces a test that is guaranteed to determine correctness under certain design for test conditions. This test generation algorithm has recently been extended to the case where the specification is non-deterministic. However, the algorithms for testing from a non-deterministic stream X-machine currently have limitations: either they test for equivalence, rather than conformance or they restrict the source of non-determinism allowed in the specification. This paper introduces a new test generation algorithm that overcomes both of these limitations, for situations where the implementation is known to be deterministic.

View graph of relations

© 2018 King's College London | Strand | London WC2R 2LS | England | United Kingdom | Tel +44 (0)20 7836 5454