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. (C) 2004 Elsevier B.V. All rights reserved.

Well quasi-orders and context-free grammars / D'Alessandro, Flavio; Stefano, Varricchio. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - 327:3(2004), pp. 255-268. (Intervento presentato al convegno 7th International Conference on Developments in Language Theory tenutosi a SZEGED, HUNGARY nel JUL 07-11, 2003) [10.1016/j.tcs.2004.03.069].

Well quasi-orders and context-free grammars

D'ALESSANDRO, Flavio;
2004

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. (C) 2004 Elsevier B.V. All rights reserved.
2004
context-free grammars; unavoidable sets of words; well quasi-orders
01 Pubblicazione su rivista::01a Articolo in rivista
Well quasi-orders and context-free grammars / D'Alessandro, Flavio; Stefano, Varricchio. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - 327:3(2004), pp. 255-268. (Intervento presentato al convegno 7th International Conference on Developments in Language Theory tenutosi a SZEGED, HUNGARY nel JUL 07-11, 2003) [10.1016/j.tcs.2004.03.069].
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/122656
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? 5
social impact