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.
Scheda prodotto non validato
Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo
Titolo: | On well Quasi-orders on languages |
Autori: | |
Data di pubblicazione: | 2003 |
Rivista: | |
Citazione: | 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. |
Handle: | http://hdl.handle.net/11573/53357 |
ISBN: | 9783540240143 |
Appartiene alla tipologia: | 04a Atto di comunicazione a congresso |