Quiescence, Fairness, Testing and the notion of Implementation

Appears: Information and Computation, 138(2):194--210, November 1997.

Also: An extended abstract appears in Proceedings of the 4th International Conference on Concurrency Theory (CONCUR '93), Hildesheim, Germany, LNCS 715, 1993.

Abstract: Two formalisms for concurrency, the Input/Output automaton model and the theory of testing, are compared and are shown to have common foundations. The relationship between the fair and quiescent preorders of I/O automata is investigated and the two preorders are shown to coincide subject to some restrictions. I/O automata are encoded into the theory of testing and the reversed must preorder is shown to be equivalent to the quiescent preorder for strongly convergent, finitely branching I/O automata up to encoding. Conversely, a theory of testing is defined directly on I/O automata, and the new reversed must preorder is shown to coincide with the quiescent preorder on strongly convergent, finitely branching I/O automata.

Download the full paper from the publisher.

Download the extended abstract from the publisher.

homepage