BIB-VERSION:: CS-TR-v2.0
          ID:: SBCS//stark/cts.dvi
       ENTRY:: July 24, 1994
ORGANIZATION:: State University of New York at Stony Brook, Computer Science
       TITLE:: Concurrent Transition Systems
        TYPE:: Preprint
      AUTHOR:: Stark, Eugene W.
     CONTACT:: Eugene W. Stark, Department of Computer Science,
                   SUNY at Stony Brook, Stony Brook, NY 11794-4400
                   Tel: 516-632-8444 <stark@cs.sunysb.edu>
	DATE:: July, 1987
   RETRIEVAL:: HTTP from BSD7.CS.SUNYSB.EDU with the URL
		   http://bsd7.cs.sunysb.edu/~stark/REPORTS/cts.ps.gz
       NOTES:: A version of this paper appeared as:
                 "Concurrent Transition Systems,"
                 Theoretical Computer Science
                 Volume 64 (1989)
                 pp. 221-269

ABSTRACT::

*Concurrent transition systems* (CTS's), are ordinary
nondeterministic transition systems that have been equipped with
additional concurrency information, specified in terms of a binary
*residual* operation on transitions.  Each CTS C freely generates
a *complete CTS* or *computation category*  C*, whose arrows are
equivalence classes of finite computation sequences, modulo a congruence
induced by the concurrency information.  The categorical composition on
C* induces a ``prefix'' partial order on its arrows, and the
*computations* of C are conveniently defined to be the ideals of this
partial order.  The definition of computations as ideals has some pleasant
properties, one of which is that the notion of a *maximal ideal* in certain
circumstances can serve as a replacement for the more troublesome notion of
a *fair computation sequence*.

To illustrate the utility of CTS's, we use them to define and
investigate a dataflow-like model of concurrent computation.  The
model consists of *machines*, which generalize the sequential
machines of classical automata theory, and various *operations*
(parallel product, input and output relabeling, and feedback) on
machines that correspond to ways of combining machines into networks.
Using our definition of computations as ideals, we define a natural
notion of *observable equivalence* of machines, and show that it
is the largest congruence, respecting parallel product and feedback,
that does not relate two machines with distinct input/output
relations.  In an attempt to obtain information about the algebra of
observable equivalence classes, we investigate a series of
abstractions of the machine model, show that these abstractions
respect the feedback operation, and characterize the homomorphic image
of this operation in each case.  A byproduct of our analysis is a
simple characterization of a large class of processes with functional
input/output behavior, and a proof that the feedback operation on such
processes obeys Kahn's fixed-point principle.

END:: SBCS//stark/cts.dvi