Recognizing Sets of Labelled Acyclic Graphs

P. Bonizzoni, G. Mauri, G. Pighizzini, and N. Sabadini

Dipartimento di Scienze dell'Informazione
Università degli Studi di Milano

Abstract

Labelled acyclic graphs with some restrictions on the labelling function can be used to describe concurrent processes. In this paper, we show how the restrictions on the labelling functions can be related with the assumptions made on the properties of the dependence and independence relations between actions. Furthermore, we compare two different recognizing devices for a particular class of labelled acyclic graphs, i.e. finite state automata on a free partially commutative monoid and finite state asynchronous automata, and give some results on the existence of minimal automata recognizing a given language.