Well quasi-orders, unavoidable sets, and derivation systems

D'Alessandro, Flavio; Varricchio, Stefano

doi:10.1051/ita:2006019

D'Alessandro, Flavio ; Varricchio, Stefano

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 40 (2006) no. 3, pp. 407-426.

Résumé

Let $I$ be a finite set of words and $\Rightarrow_{I}^{*}$ be the derivation relation generated by the set of productions ${ϵ \to u ∣ u \in I}$ . Let $L_{I}^{ϵ}$ be the set of words $u$ such that $ϵ \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}^{ϵ}$ . This result generalizes a theorem of [Ehrenfeucht et al., Theor. Comput. Sci. 27 (1983) 311-332]. Further generalizations are investigated.

Zbl

DOI : 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
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/

Bibliographie
Cité par

[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 | Zbl

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

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

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

[5] A. De Luca and S. Varricchio, Well quasi-orders and regular languages. Acta Inform. 31 (1994) 539-557. | MR | Zbl

[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 | Zbl

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

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

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

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

[11] L. Ilie and A. Salomaa, On well quasi orders of free monoids. Theor. Comput. Sci. 204 (1998) 131-152. | Zbl

[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

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

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

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

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

Cité par Sources :