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.
Bonizzoni, P., Mauri, G., Pighizzini, G., Sabadini, N. (1992). Recognizing sets of labelled acyclic graphs. In Nivat M, A. Podelski (a cura di), Tree automata and languages (pp. 201-224). Amsterdam : North-Holland.
Recognizing sets of labelled acyclic graphs
BONIZZONI, PAOLA;MAURI, GIANCARLO;
1992
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.