Abstract
This paper studies testing based on labelled transition systems, using the assumption that implementations communicate with their environment via inputs and outputs. Such implementations are formalized by restricting the class of transition systems to those systems that can always accept input actions, as in input/output automata. Implementation relations, formalizing the notion of conformance of these implementations with respect to labelled transition system specifications, are defined analogous to the theory of testing equivalence and preorder. A test generation algorithm is given, which is proved to produce a sound and exhaustive test suite from a specification, i.e., a test suite that fully characterizes the set of correct implementations.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
G. Bernot. Testing against formal specifications: A theoretical view. In S. Abramsky and T. S. E. Maibaum, eds., TAPSOFT'91, 99–119. LNCS 494, Springer-Verlag, 1991.
E. Brinksma. A theory for the derivation of tests. In S. Aggarwal and K. Sabnani, eds., Prot. Spec., Test., and Ver. VIII, 63–74. North-Holland, 1988.
E. Brinksma, R. Alderden, R. Langerak, J. van de Lagemaat, and J. Tretmans. A formal approach to conformance testing. In J. de Meer, et al., eds., Protocol Test Systems II, 349–363. North-Holland, 1990.
ITU-T. SDL. Recommendation Z.100, 1992.
R. De Nicola. Extensional equivalences for transition systems. Acta Informatica, 24:211–237, 1987.
R. De Nicola and R. Segala. A process algebraic view of input/output automata. TCS, 138:391–423, 1995.
R.J. van Glabbeek. The linear time — branching time spectrum. In J.C.M. Baeten and J.W. Klop, eds., CONCUR'90, LNCS 458, 278–297. Springer-Verlag, 1990.
ISO. Estelle — International Standard IS-9074, 1989.
ISO. LOTOS — International Standard IS-8807, 1989.
ISO/IEC JTC1/SC21 WG7, ITU-T SG 10/Q.8. Formal Methods in Conformance Testing, working draft. September 1995.
G. Leduc. A framework based on implementation relations for implementing LOTOS specifications. Computer Networks and ISDN Systems, 25(1):23–41, 1992.
N.A. Lynch and M.R. Tuttle. An introduction to input/output automata. CWI Quarterly, 2(3):219–246, 1989.
M. Phalippou. Relations d'Implantation et Hypothèses de Test sur des Automates à Entrées et Sorties. PhD thesis, L'Université de Bordeaux I (F), 1994.
R. Segala. Quiescence, fairness, testing, and the notion of implementation. In E. Best, ed., CONCUR'93, 324–338. LNCS 715, Springer-Verlag, 1993.
J. Tretmans. A Formal Approach to Conformance Testing. PhD thesis, University of Twente (NL), 1992.
J. Tretmans. Testing labelled transition systems with inputs and outputs. Memorandum INF-95-26, University of Twente (NL), 1995.
J. Tretmans and L.Verhaard. A queue model relating synchronous and asynchronous communication. In R.J. Linn and M.ü. Uyar, eds., Prot. Spec., Test., and Ver. XII, 131–145. North-Holland, 1992.
F. Vaandrager. On the relationship between process algebra and input/output automata. In Logic in Computer Science, 387–398. Sixth Annual IEEE Symposium, 1991.
C. D. Wezeman. The CO-OP method for compositional derivation of conformance testers. In E. Brinksma, et al., eds., Prot. Spec., Test., and Ver. IX, 145–158. North-Holland, 1990.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1996 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Tretmans, J. (1996). Test generation with inputs, outputs, and quiescence. In: Margaria, T., Steffen, B. (eds) Tools and Algorithms for the Construction and Analysis of Systems. TACAS 1996. Lecture Notes in Computer Science, vol 1055. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-61042-1_42
Download citation
DOI: https://doi.org/10.1007/3-540-61042-1_42
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-61042-7
Online ISBN: 978-3-540-49874-2
eBook Packages: Springer Book Archive