Abstract
This paper develops a new testing-based semantic theory of processes that aims to circumvent difficulties that traditional testing/failures theories have in dealing with divergent behavior. Our framework incorporates a notion of fairness into the determination of when a process passes a test; we contrast this definition with existing approaches and give characterizations of the induced semantic preorders. An example highlights the utility of our results.
Research supported by NSF grant CCR-9120995, ONR Young Investigator Award N00014-92-J-1582, NSF Young Investigator Award CCR-9257963, and NSF grant CCR-9402807.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
J.C.M. Baeten, editor. Applications of Process Algebra, vol. 17 of Cambridge Tracts in Theoretical Computer Science. Cambridge Press, Cambridge, 1990.
J.A. Bergstra, J.W. Klop, and E.-R. Olderog. Failures without chaos: A new process semantics for fair abstraction. In M. Wirsing, editor, Formal Description Techniques—III, pages 77–103. North-Holland, 1987.
E. Best. Fairness and conspiracies. Inf. Proc. Letters, 18:215–220, 1984.
S.D. Brookes, C.A.R. Hoare, and A.W. Roscoe. A theory of communicating sequential processes. Journal of the ACM, 31(3):560–599, July 1984.
R. Cleaveland, J. Parrow, and B. Steifen. The Concurrency Workbench: A semantics-based tool for the verification of finite-state systems. ACM Trans. on Prog. Lang. and Sys., 15(1):36–72, January 1993.
G. Costa and C. Stirling. Weak and strong fairness in CCS. Inf. and Comp., 87:207–244, 1987.
R. De Nicola. Extensional equivalences for transition systems. Acta Inf., 1987.
R. De Nicola and M.C.B. Hennessy. Testing equivalences for processes. Theoret. Comp. Sci., 34:83–133, 1983.
N. Francez. Fairness. Springer-Verlag, 1986.
M.C.B. Hennessy. An algebraic theory of fair asynchronous communicating processes. Theoret. Comp. Sci., 49:121–143, 1987.
M.C.B. Hennessy. Algebraic Theory of Processes. MIT Press, Boston, 1988.
C.J. Koomen. Algebraic specification and verification of communications protocols. Science of Comp. Prog., 5:1–36, 1985.
R. Milner. Communication and Concurrency. Prentice-Hall, London, 1989.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1995 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Natarajan, V., Cleaveland, R. (1995). Divergence and fair testing. In: Fülöp, Z., Gécseg, F. (eds) Automata, Languages and Programming. ICALP 1995. Lecture Notes in Computer Science, vol 944. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-60084-1_112
Download citation
DOI: https://doi.org/10.1007/3-540-60084-1_112
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-60084-8
Online ISBN: 978-3-540-49425-6
eBook Packages: Springer Book Archive