QUIESCENCE, FAIRNESS, TESTING, AND THE NOTION OF IMPLEMENTATION

Two formalisms for concurrency, the Input/Output automaton model and t he theory of testing, are compared and are shown to have common founda tions. 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 theor y 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 define d directly on I/O automata, and the new reversed MUST preorder is show n to coincide with the quiescent preorder on strongly convergent, fini tely branching I/O automata. (C) 1997 Academic Press.