Well quasi-orders, unavoidable sets, and derivation systems
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 40 (2006) no. 3, pp. 407-426.

Let I be a finite set of words and I * be the derivation relation generated by the set of productions {ϵuuI}. 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.

DOI : https://doi.org/10.1051/ita:2006019
Classification : 68Q45,  68R15
Mots clés : well quasi-orders, context-free languages
@article{ITA_2006__40_3_407_0,
     author = {D'Alessandro, Flavio and Varricchio, Stefano},
     title = {Well quasi-orders, unavoidable sets, and derivation systems},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {407--426},
     publisher = {EDP-Sciences},
     volume = {40},
     number = {3},
     year = {2006},
     doi = {10.1051/ita:2006019},
     zbl = {1110.68060},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ita:2006019/}
}
TY  - JOUR
AU  - D'Alessandro, Flavio
AU  - Varricchio, Stefano
TI  - Well quasi-orders, unavoidable sets, and derivation systems
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2006
DA  - 2006///
SP  - 407
EP  - 426
VL  - 40
IS  - 3
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita:2006019/
UR  - https://zbmath.org/?q=an%3A1110.68060
UR  - https://doi.org/10.1051/ita:2006019
DO  - 10.1051/ita:2006019
LA  - en
ID  - ITA_2006__40_3_407_0
ER  - 
D'Alessandro, Flavio; Varricchio, Stefano. Well quasi-orders, unavoidable sets, and derivation systems. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 40 (2006) no. 3, pp. 407-426. doi : 10.1051/ita:2006019. http://www.numdam.org/articles/10.1051/ita:2006019/

[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. | MR 1196555 | Zbl 0759.68049

[2] F. D'Alessandro and S. Varricchio, On well quasi-orders on languages. Lect. Notes Comput. Sci. 2710 (2003) 230-241, | MR 2054367 | Zbl 1037.68080

[3] F. D'Alessandro and S. Varricchio, Well quasi-orders and context-free grammars. Theor. Comput. Sci. 327 (2004) 255-268. | MR 2098308 | Zbl 1071.68033

[4] A. De Luca and S. Varricchio, Some regularity conditions based on well quasi-orders. Lect. Notes Comput. Sci. 583 (1992) 356-371. | MR 1253366

[5] A. De Luca and S. Varricchio, Well quasi-orders and regular languages. Acta Inform. 31 (1994) 539-557. | MR 1300055 | Zbl 0818.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). | MR 1696498 | Zbl 0935.68056

[7] A. Ehrenfeucht, D. Haussler and G. Rozenberg, On regularity of context-free languages. Theor. Comput. Sci. 27 (1983) 311-332. | MR 731068 | Zbl 0553.68044

[8] T. Harju and L. Ilie, On well quasi orders of words and the confluence property. Theor. Comput. Sci. 200 (1998) 205-224. | MR 1625519 | Zbl 0915.68104

[9] D. Haussler, Another generalization of Higman’s well quasi-order result on Σ * . Discrete Math. 57 (1985) 237-243. | MR 816812 | Zbl 0583.68039

[10] G.H. Higman, Ordering by divisibility in abstract algebras. Proc. London Math. Soc. 3 (1952) 326-336. | Zbl 0047.03402

[11] L. Ilie and A. Salomaa, On well quasi orders of free monoids. Theor. Comput. Sci. 204 (1998) 131-152. | Zbl 0913.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. | Zbl 0958.68086

[13] M. Ito, L. Kari and G. Thierrin, Shuffle and scattered deletion closure of languages. Theor. Comput. Sci. 245 (2000) 115-133. | Zbl 0946.68074

[14] M. Jantzen, Extending regular expressions with iterated shuffle. Theor. Comput. Sci. 38 (1985) 223-247. | Zbl 0574.68069

[15] J. Kruskal, The theory of well quasi-ordering: a frequently discovered concept. J. Combin. Theory Ser. A 13 (1972) 297-305. | Zbl 0244.06002

[16] L. Puel, Using unavoidable sets of trees to generalize Kruskal's theorem. J. Symbolic Comput. 8 (1989) 335-382. | Zbl 0676.06003

Cité par Sources :