Well quasi-orders, unavoidable sets, and derivation systems

D'Alessandro, Flavio; Varricchio, Stefano

doi:10.1051/ita:2006019

Geodesic

Parcourir par

Well quasi-orders, unavoidable sets, and derivation systems

D'Alessandro, Flavio ; Varricchio, Stefano

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

Voir la notice de l'article provenant de la source Numdam

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
Keywords: 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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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

Cité par Sources :