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.
Capitolo o saggio
Tree automata; Acyclic graphs
English
Tree automata and languages
978-0-444-89026-9
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.
Bonizzoni, P; Mauri, G; Pighizzini, G; Sabadini, N
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/16947
Citazioni
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
Social impact