Synthesis of Nondeterministic Asynchronous Automata
Giovanni Pighizzini
Dipartimento di Scienze dell'Informazione
Università degli Studi di Milano
via Comelico 39 -- 20135 Milano, Italy
Abstract
In this paper we state a new characterization of the class of
recognizable trace languages [Mazurkievick 1977]: we prove that this
class coincides with the minimal class of trace languages containing finite languages and
closed under union, product and two new operations called $\alpha$-restriction
and restricted iteration. Using this characterization,
we give a ``modular'' construction of an asynchronous automaton [Zielonka 1986]
accepting a given recognizable trace language.
Download
Compressed postscript
Compressed dvi