Unavoidable languages, cuts and innocent sets of words
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 29 (1995) no. 5, pp. 339-382. 
@article{ITA_1995__29_5_339_0,
     author = {Rosaz, L.},
     title = {Unavoidable languages, cuts and innocent sets of words},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {339--382},
     publisher = {EDP-Sciences},
     volume = {29},
     number = {5},
     year = {1995},
     mrnumber = {1360665},
     zbl = {0838.68068},
     language = {en},
     url = {http://www.numdam.org/item/ITA_1995__29_5_339_0/}
}
TY  - JOUR
AU  - Rosaz, L.
TI  - Unavoidable languages, cuts and innocent sets of words
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 1995
SP  - 339
EP  - 382
VL  - 29
IS  - 5
PB  - EDP-Sciences
UR  - http://www.numdam.org/item/ITA_1995__29_5_339_0/
LA  - en
ID  - ITA_1995__29_5_339_0
ER  - 
%0 Journal Article
%A Rosaz, L.
%T Unavoidable languages, cuts and innocent sets of words
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 1995
%P 339-382
%V 29
%N 5
%I EDP-Sciences
%U http://www.numdam.org/item/ITA_1995__29_5_339_0/
%G en
%F ITA_1995__29_5_339_0
Rosaz, L. Unavoidable languages, cuts and innocent sets of words. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 29 (1995) no. 5, pp. 339-382. http://www.numdam.org/item/ITA_1995__29_5_339_0/

1. A. V. Aho and M. J. Corasick, Efficient string machines, an aid to bibliographic research, Comm. ACM, 1975, 18 (6), pp. 333-340. | MR | Zbl

2. D. R. Bean, A. Ehrenfeucht and G. F. Mcnulty, Avoidable patterns in strings of symbols, Pacific J. Math., 1979, 85, 2, pp. 261-294. | MR | Zbl

3. W. Bucher, A. Ehrenfeucht and D. Haussler, On Total Regulators Generated by Derivation Relations, Proc. of 12th International Colloquium on Automata, Languages and Programming; Lectures notes in Computer Science, 194, Springer-Verlag, 1985, pp, 71-79. | MR | Zbl

4. C. Choffrut and K. Culik, On extendibility of unavoidable sets, Discrete Applied Mathematics, 1984, pp. 125-137. | MR | Zbl

5. M. Crochemore, M. Lerest and P. Wender, An optimal test on finite unavoidable sets of words, Information Processing Letter, 1983, 16, pp. 179-180. | MR | Zbl

6. A. Ehrenfeuch, D. Haussler and G. Rozenberg, On regularity of context-free languages, Theor Comp. Sci., 1983, 27, pp. 311-332. | MR | Zbl

7. N. J. Fine and H. S. Wilf, Uniqueness Theorem for Periodic functions, Proc. Am. Math. Soc., 1965, 16, pp. 109-114. | MR | Zbl

8. G. Higman, Ordering by divisibility in abstract algebras, Proc. London Math. Soc., 1952, 2, pp. 326-336. | MR | Zbl

9. Kruskal, Well-quasi ordering, The Tree Theorem, and Vazsonyi's conjecture, Trans. Amer. Math. Soc., 1960, 95, pp. 210-225. | MR | Zbl

10. Kruskal, The theory of well-quasi ordering: a frequently discovered concept, J. Comb. Theory Ser., 1972, A 13 (3), pp. 297-305. | MR | Zbl

11. G. Kucherov and M. Rusinovitch, On Ground-Reducibility Problem for Word Rewriting Systems with Variables, In E. DEATON and R. WILKERSON, eds., Proceedings 1994 ACM/SIGAPP Symposium on Applied Computing, Phoenix, March 1994, ACM-Press.

12. G. Kucherov and M. Rusinovitch, Complexity of Testing Ground Reducibility for Linear Word Rewriting Systems with Variables, preprint.

13. Lothaire, Combinatorics on words, chapter 1, Add.-Wesley, by D. PERRIN, 1983. | MR | Zbl

14. ld, chapter 6, by J. Sakarovitch.

15. E. Ochmanski, Inevitability in concurrent Systems, IPL 25, 1987, pp. 221-225. | MR | Zbl

16. L. Puel, Using unavoidable sets of trees to generalize Kruskal's theorem, J.S.C., 1989, Vol. 8, No. 4, pp. 335-382. | MR | Zbl

17. L. Rosaz, Inventories of unavoidable languages and the word-extension conjecture, to appear in Theoretical Computer Science. | MR | Zbl

18. L. Rosaz, Unavoidable languages, Mémoire de thèse, LITP Report.

19. M. P. Schutzenberger, On the synchronizing properties of certain prefix codes, Information and Control, 1964, 7, pp. 23-36. | MR | Zbl