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.  
  2. F. D'Alessandro and S. Varricchio, On well quasi-orders on languages. Lect. Notes Comput. Sci.2710 (2003) 230–241,  
  3. F. D'Alessandro and S. Varricchio, Well quasi-orders and context-free grammars. Theor. Comput. Sci.327 (2004) 255–268.  
  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.  
  6. A. de Luca and S. Varricchio, Finiteness and regularity in semigroups and formal languages. EATCS Monographs on Theoretical Computer Science, Springer, Berlin (1999).  
  7. A. Ehrenfeucht, D. Haussler and G. Rozenberg, On regularity of context-free languages. Theor. Comput. Sci.27 (1983) 311–332.  
  8. T. Harju and L. Ilie, On well quasi orders of words and the confluence property. Theor. Comput. Sci.200 (1998) 205–224.  
  9. D. Haussler, Another generalization of Higman's well quasi-order result on ∑*. Discrete Math.57 (1985) 237–243.  
  10. G.H. Higman, Ordering by divisibility in abstract algebras. Proc. London Math. Soc.3 (1952) 326–336.  
  11. L. Ilie and A. Salomaa, On well quasi orders of free monoids. Theor. Comput. Sci.204 (1998) 131–152.  
  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.  
  13. M. Ito, L. Kari and G. Thierrin, Shuffle and scattered deletion closure of languages. Theor. Comput. Sci.245 (2000) 115–133.  
  14. M. Jantzen, Extending regular expressions with iterated shuffle. Theor. Comput. Sci.38 (1985) 223–247.  
  15. J. Kruskal, The theory of well quasi-ordering: a frequently discovered concept. J. Combin. Theory Ser. A13 (1972) 297–305.  
  16. L. Puel, Using unavoidable sets of trees to generalize Kruskal's theorem. J. Symbolic Comput.8 (1989) 335–382.  

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.