Let G be a context-free grammar and let L be the language of all the words derived from any variable of G. We prove the following generalization of Higman's theorem: any division order on L is a well quasi-order on L. We also give applications of this result to some quasi-orders associated with unitary grammars. © Springer-Verlag Berlin Heidelberg 2003.
On well Quasi-orders on languages / D'Alessandro, Flavio; S., Varricchio. - STAMPA. - 2710:(2003), pp. 230-241. (Intervento presentato al convegno DLT 2003, tenutosi a Developments in Language Theory, SZEGED, HUNGARY nel 7-11 luglio 2003).
On well Quasi-orders on languages
D'ALESSANDRO, Flavio;
2003
Abstract
Let G be a context-free grammar and let L be the language of all the words derived from any variable of G. We prove the following generalization of Higman's theorem: any division order on L is a well quasi-order on L. We also give applications of this result to some quasi-orders associated with unitary grammars. © Springer-Verlag Berlin Heidelberg 2003.File allegati a 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.
