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