Article contents
Well quasi-orders, unavoidable sets, and derivation systems
Published online by Cambridge University Press: 18 October 2006
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.
- Type
- Research Article
- Information
- RAIRO - Theoretical Informatics and Applications , Volume 40 , Issue 3: Word Avoidability Complexity And Morphisms (WACAM) , July 2006 , pp. 407 - 426
- Copyright
- © EDP Sciences, 2006
References
- 3
- Cited by