Approximation of a trace, asynchronous automata and the ordering of events in a distributed system. (English) Zbl 0656.68060

Automata, languages and programming, Proc. 15th Int. Colloq., Tampere/Finn. 1988, Lect. Notes Comput. Sci. 317, 147-161 (1988).
[For the entire collection see Zbl 0639.00042.]
The notion of trace was introduced in order to modelize the concurrency of actions. A trace is an element of the quotient of the free monoid by the congruence generated by a finite set of relations of the form \(ab\sim ba.\) We introduce the notion of the approximation of a trace and we study its properties. The main result is the existence of an asynchronous automaton which recognizes the set of traces corresponding to an approximation. We give two applications: the first one is a new proof of Zielonka’s theorem [W. Zielonka, RAIRO, Inf. Théor. Appl. 21, 99- 135 (1987; Zbl 0623.68055)], and the second one is an algorithm for the ordering of events in a distributed system.


68Q45 Formal languages and automata
68N25 Theory of operating systems
20M35 Semigroups in automata theory, linguistics, etc.