# 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

## Access Full Article

top## Abstract

top## How to cite

topD'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- 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
- F. D'Alessandro and S. Varricchio, On well quasi-orders on languages. Lect. Notes Comput. Sci.2710 (2003) 230–241, Zbl1037.68080
- F. D'Alessandro and S. Varricchio, Well quasi-orders and context-free grammars. Theor. Comput. Sci.327 (2004) 255–268. Zbl1071.68033
- A. de Luca and S. Varricchio, Some regularity conditions based on well quasi-orders. Lect. Notes Comput. Sci.583 (1992) 356–371.
- A. de Luca and S. Varricchio, Well quasi-orders and regular languages. Acta Inform.31 (1994) 539–557. Zbl0818.68115
- 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
- A. Ehrenfeucht, D. Haussler and G. Rozenberg, On regularity of context-free languages. Theor. Comput. Sci.27 (1983) 311–332. Zbl0553.68044
- T. Harju and L. Ilie, On well quasi orders of words and the confluence property. Theor. Comput. Sci.200 (1998) 205–224. Zbl0915.68104
- D. Haussler, Another generalization of Higman's well quasi-order result on ∑*. Discrete Math.57 (1985) 237–243. Zbl0583.68039
- G.H. Higman, Ordering by divisibility in abstract algebras. Proc. London Math. Soc.3 (1952) 326–336. Zbl0047.03402
- L. Ilie and A. Salomaa, On well quasi orders of free monoids. Theor. Comput. Sci.204 (1998) 131–152. Zbl0913.68114
- 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
- M. Ito, L. Kari and G. Thierrin, Shuffle and scattered deletion closure of languages. Theor. Comput. Sci.245 (2000) 115–133. Zbl0946.68074
- M. Jantzen, Extending regular expressions with iterated shuffle. Theor. Comput. Sci.38 (1985) 223–247. Zbl0574.68069
- J. Kruskal, The theory of well quasi-ordering: a frequently discovered concept. J. Combin. Theory Ser. A13 (1972) 297–305. Zbl0244.06002
- L. Puel, Using unavoidable sets of trees to generalize Kruskal's theorem. J. Symbolic Comput.8 (1989) 335–382. Zbl0676.06003

## NotesEmbed ?

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