On well Quasi-orders on languages
Flavio D’Alessandro, Stefano Varricchio · IRIS Research product catalog (Sapienza University of Rome) · 2003
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.