Well quasi-orders, unavoidable sets, and derivation systems

Flavio D'Alessandro; Stefano Varricchio

RAIRO - Theoretical Informatics and Applications (2006)

  • Volume: 40, Issue: 3, page 407-426
  • ISSN: 0988-3754

Abstract

top
Let I be a finite set of words and I * be the derivation relation generated by the set of productions {ε → u | u ∈ I}. Let L I ϵ be the set of words u such that ϵ I * u . We prove that the set I is unavoidable if and only if the relation I * is a well quasi-order on the set L I ϵ . This result generalizes a theorem of [Ehrenfeucht et al.,Theor. Comput. Sci.27 (1983) 311–332]. Further generalizations are investigated.

How to cite

top

D'Alessandro, Flavio, and Varricchio, Stefano. "Well quasi-orders, unavoidable sets, and derivation systems." RAIRO - Theoretical Informatics and Applications 40.3 (2006): 407-426. <http://eudml.org/doc/249708>.

@article{DAlessandro2006,
abstract = { Let I be a finite set of words and $\Rightarrow_I^*$ be the derivation relation generated by the set of productions \{ε → u | u ∈ I\}. Let $L_I^\{\epsilon\}$ be the set of words u such that $\epsilon \Rightarrow_I^* u$. We prove that the set I is unavoidable if and only if the relation $\Rightarrow_I^*$ is a well quasi-order on the set $L_I^\{\epsilon\}$. This result generalizes a theorem of [Ehrenfeucht et al.,Theor. Comput. Sci.27 (1983) 311–332]. Further generalizations are investigated. },
author = {D'Alessandro, Flavio, Varricchio, Stefano},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Well quasi-orders; context-free languages.; well quasi-orders; context-free languages},
language = {eng},
month = {10},
number = {3},
pages = {407-426},
publisher = {EDP Sciences},
title = {Well quasi-orders, unavoidable sets, and derivation systems},
url = {http://eudml.org/doc/249708},
volume = {40},
year = {2006},
}

TY - JOUR
AU - D'Alessandro, Flavio
AU - Varricchio, Stefano
TI - Well quasi-orders, unavoidable sets, and derivation systems
JO - RAIRO - Theoretical Informatics and Applications
DA - 2006/10//
PB - EDP Sciences
VL - 40
IS - 3
SP - 407
EP - 426
AB - Let I be a finite set of words and $\Rightarrow_I^*$ be the derivation relation generated by the set of productions {ε → u | u ∈ I}. Let $L_I^{\epsilon}$ be the set of words u such that $\epsilon \Rightarrow_I^* u$. We prove that the set I is unavoidable if and only if the relation $\Rightarrow_I^*$ is a well quasi-order on the set $L_I^{\epsilon}$. This result generalizes a theorem of [Ehrenfeucht et al.,Theor. Comput. Sci.27 (1983) 311–332]. Further generalizations are investigated.
LA - eng
KW - Well quasi-orders; context-free languages.; well quasi-orders; context-free languages
UR - http://eudml.org/doc/249708
ER -

References

top
  1. D.P. Bovet and S. Varricchio, On the regularity of languages on a binary alphabet generated by copying systems. Inform. Process. Lett.44 (1992) 119–123.  Zbl0759.68049
  2. F. D'Alessandro and S. Varricchio, On well quasi-orders on languages. Lect. Notes Comput. Sci.2710 (2003) 230–241,  Zbl1037.68080
  3. F. D'Alessandro and S. Varricchio, Well quasi-orders and context-free grammars. Theor. Comput. Sci.327 (2004) 255–268.  Zbl1071.68033
  4. A. de Luca and S. Varricchio, Some regularity conditions based on well quasi-orders. Lect. Notes Comput. Sci.583 (1992) 356–371.  
  5. A. de Luca and S. Varricchio, Well quasi-orders and regular languages. Acta Inform.31 (1994) 539–557.  Zbl0818.68115
  6. A. de Luca and S. Varricchio, Finiteness and regularity in semigroups and formal languages. EATCS Monographs on Theoretical Computer Science, Springer, Berlin (1999).  Zbl0935.68056
  7. A. Ehrenfeucht, D. Haussler and G. Rozenberg, On regularity of context-free languages. Theor. Comput. Sci.27 (1983) 311–332.  Zbl0553.68044
  8. T. Harju and L. Ilie, On well quasi orders of words and the confluence property. Theor. Comput. Sci.200 (1998) 205–224.  Zbl0915.68104
  9. D. Haussler, Another generalization of Higman's well quasi-order result on ∑*. Discrete Math.57 (1985) 237–243.  Zbl0583.68039
  10. G.H. Higman, Ordering by divisibility in abstract algebras. Proc. London Math. Soc.3 (1952) 326–336.  Zbl0047.03402
  11. L. Ilie and A. Salomaa, On well quasi orders of free monoids. Theor. Comput. Sci.204 (1998) 131–152.  Zbl0913.68114
  12. B. Intrigila and S. Varricchio, On the generalization of Higman and Kruskal's theorems to regular languages and rational trees. Acta Inform.36 (2000) 817–835.  Zbl0958.68086
  13. M. Ito, L. Kari and G. Thierrin, Shuffle and scattered deletion closure of languages. Theor. Comput. Sci.245 (2000) 115–133.  Zbl0946.68074
  14. M. Jantzen, Extending regular expressions with iterated shuffle. Theor. Comput. Sci.38 (1985) 223–247.  Zbl0574.68069
  15. J. Kruskal, The theory of well quasi-ordering: a frequently discovered concept. J. Combin. Theory Ser. A13 (1972) 297–305.  Zbl0244.06002
  16. L. Puel, Using unavoidable sets of trees to generalize Kruskal's theorem. J. Symbolic Comput.8 (1989) 335–382.  Zbl0676.06003

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.