Synthesis of Nondeterministic Asynchronous Automata

Giovanni Pighizzini

Dipartimento di Scienze dell'Informazione
Università degli Studi di Milano
via Comelico 39 -- 20135 Milano, Italy
In this paper we state a new characterization of the class of recognizable trace languages: 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 accepting a given recognizable trace language.

Compressed postscript
Compressed dvi