Let be a finite set of words and be the derivation relation generated by the set of productions . Let be the set of words such that . We prove that the set is unavoidable if and only if the relation is a well quasi-order on the set . This result generalizes a theorem of [Ehrenfeucht et al., Theor. Comput. Sci. 27 (1983) 311-332]. Further generalizations are investigated.
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 SP - 407 EP - 426 VL - 40 IS - 3 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ita:2006019/ DO - 10.1051/ita:2006019 LA - en ID - ITA_2006__40_3_407_0 ER -
%0 Journal Article %A D'Alessandro, Flavio %A Varricchio, Stefano %T Well quasi-orders, unavoidable sets, and derivation systems %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2006 %P 407-426 %V 40 %N 3 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ita:2006019/ %R 10.1051/ita:2006019 %G en %F ITA_2006__40_3_407_0
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] On the regularity of languages on a binary alphabet generated by copying systems. Inform. Process. Lett. 44 (1992) 119-123. | MR | Zbl
and ,[2] On well quasi-orders on languages. Lect. Notes Comput. Sci. 2710 (2003) 230-241, | MR | Zbl
and ,[3] Well quasi-orders and context-free grammars. Theor. Comput. Sci. 327 (2004) 255-268. | MR | Zbl
and ,[4] Some regularity conditions based on well quasi-orders. Lect. Notes Comput. Sci. 583 (1992) 356-371. | MR
and ,[5] Well quasi-orders and regular languages. Acta Inform. 31 (1994) 539-557. | MR | Zbl
and ,[6] Finiteness and regularity in semigroups and formal languages. EATCS Monographs on Theoretical Computer Science, Springer, Berlin (1999). | MR | Zbl
and ,[7] On regularity of context-free languages. Theor. Comput. Sci. 27 (1983) 311-332. | MR | Zbl
, and ,[8] On well quasi orders of words and the confluence property. Theor. Comput. Sci. 200 (1998) 205-224. | MR | Zbl
and ,[9] Another generalization of Higman’s well quasi-order result on . Discrete Math. 57 (1985) 237-243. | MR | Zbl
,[10] Ordering by divisibility in abstract algebras. Proc. London Math. Soc. 3 (1952) 326-336. | Zbl
,[11] On well quasi orders of free monoids. Theor. Comput. Sci. 204 (1998) 131-152. | Zbl
and ,[12] On the generalization of Higman and Kruskal's theorems to regular languages and rational trees. Acta Inform. 36 (2000) 817-835. | Zbl
and ,[13] Shuffle and scattered deletion closure of languages. Theor. Comput. Sci. 245 (2000) 115-133. | Zbl
, and ,[14] Extending regular expressions with iterated shuffle. Theor. Comput. Sci. 38 (1985) 223-247. | Zbl
,[15] The theory of well quasi-ordering: a frequently discovered concept. J. Combin. Theory Ser. A 13 (1972) 297-305. | Zbl
,[16] Using unavoidable sets of trees to generalize Kruskal's theorem. J. Symbolic Comput. 8 (1989) 335-382. | Zbl
,Cité par Sources :