On Well Quasi-orders on Languages

  • Flavio D’Alessandro
  • Stefano Varricchio
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 2710)


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.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    J. Berstel, Transductions and Context-Free Languages. Teubner, Stuttgart, 1979.zbMATHGoogle Scholar
  2. 2.
    D.P. Bovet and S. Varricchio, On the regularity of languages on a binary alphabet generated by copying systems. Information Processing Letters 44, 119–123 (1992).zbMATHCrossRefMathSciNetGoogle Scholar
  3. 3.
    A. de Luca and S. Varricchio, Some regularity conditions based on well quasi-orders. Lecture Notes in Computer Science, Vol. 583, pp. 356–371, Springer-Verlag, Berlin, 1992.Google Scholar
  4. 4.
    A. de Luca and S. Varricchio, Well quasi-orders and regular languages. Acta Informatica 31, 539–557 (1994).CrossRefMathSciNetGoogle Scholar
  5. 5.
    A. de Luca and S. Varricchio, Finiteness and regularity in semigroups and formal languages. EATCS Monographs on Theoretical Computer Science. Springer, Berlin, 1999.Google Scholar
  6. 6.
    A. Ehrenfeucht, D. Haussler, and G. Rozenberg, On regularity of context-free languages. Theoretical Computer Science 27, 311–332 (1983).zbMATHCrossRefMathSciNetGoogle Scholar
  7. 7.
    T. Harju and L. Ilie, On well quasi orders of words and the confluence property. Theoretical Computer Science 200, 205–224 (1998).zbMATHCrossRefMathSciNetGoogle Scholar
  8. 8.
    D. Haussler, Another generalization of Higman’s well quasi-order result on Σ*. Discrete Mathematics 57, 237–243 (1985).zbMATHCrossRefMathSciNetGoogle Scholar
  9. 9.
    G. H. Higman, Ordering by divisibility in abstract algebras. Proc. London Math. Soc. 3, 326–336 (1952).CrossRefMathSciNetGoogle Scholar
  10. 10.
    L. Ilie and A. Salomaa, On well quasi orders of free monoids. Theoretical Computer Science 204, 131–152 (1998).zbMATHCrossRefMathSciNetGoogle Scholar
  11. 11.
    B. Intrigila and S. Varricchio, On the generalization of Higman and Kruskal’s theorems to regular languages and rational trees. Acta Informatica 36, 817–835 (2000).zbMATHCrossRefMathSciNetGoogle Scholar
  12. 12.
    J. Kruskal, The theory of well-quasi-ordering: a frequently discovered concept. J. Combin. Theory, Ser. A, 13, 297–305 (1972).zbMATHCrossRefMathSciNetGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2003

Authors and Affiliations

  • Flavio D’Alessandro
    • 1
  • Stefano Varricchio
    • 2
  1. 1.Dipartimento di MatematicaUniversità di Roma “La Sapienza”RomaItaly
  2. 2.Dipartimento di MatematicaUniversità di Roma “Tor Vergata”RomaItaly

Personalised recommendations