Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

On Well Quasi-orders on Languages

Flavio D’AlessandroContact Information and Stefano VarricchioContact Information

(5)  Dipartimento di Matematica, Università di Roma “La Sapienza”, Piazzale Aldo Moro 2, 00185 Roma, Italy
(6)  Dipartimento di Matematica, Università di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma, Italy
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.
This work was partially supported by MIUR project “Linguaggi formali e automi: teoria e applicazioni”.

Contact Information Flavio D’Alessandro
Email: dalessan@mat.uniroma1.it
URL: http://mat.uniroma1.it/people/dalessandro

Contact Information Stefano Varricchio
Email: varricch@mat.uniroma2.it
URL: http://mat.uniroma2.it/~varricch
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Referenced by
1 newer article

  1. D'Alessandro, Flavio (2006) Well quasi-orders, unavoidable sets, and derivation systems. RAIRO - Theoretical Informatics and Applications 40(3)
    [CrossRef]
Remote Address: 38.107.191.106 • Server: mpweb04
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)