Concurrent transition systems (Q1119395): Difference between revisions

The author was led to define concurrent transition systems (CTS for short) because of the apparent difficulty of establishing relationships between operational and denotational models of concurrent computation. A CTS is an ordinary nondeterministic transition system provided with additional concurrency information. This concurrency information is specified in terms of a binary residual operation on transitions, which describes how certain pairs of transitions ``commute''. The defining axioms for a CTS generate a rich algebraic theory, minutely developed. 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 residual operation. The notion ``computation tree'' for ordinary transition systems generalized at computation diagram for CTS's, leading to computation convenient definition of a CTS as the ideals of its computation diagram. A pleasant property of this definition is that the notion of a maximal ideal in certain circumstances can serve as replacement for the most troublesome notion of a fair computation sequence. To illustrate CTS utility, the author use them to define and investigate a dataflow-like model of concurrent computation.