Unavoidable languages, cuts and innocent sets of words

 Access to full text

 Full (PDF)

1. 1. A. V. AHO and M. J. CORASICK, Efficient string machines, an aid to bibliographic research, Comm. ACM, 1975, 18 (6), pp. 333-340. Zbl0301.68048MR371172
2. 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. Zbl0428.05001MR574919
3. 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. Zbl0571.68056MR819242
4. 4. C. CHOFFRUT and K. CULIK, On extendibility of unavoidable sets, Discrete Applied Mathematics, 1984, pp. 125-137. Zbl0629.68080MR761597
5. 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. Zbl0506.68057MR707587
6. 6. A. EHRENFEUCH, D. HAUSSLER and G. ROZENBERG, On regularity of context-free languages, Theor Comp. Sci., 1983, 27, pp. 311-332. Zbl0553.68044MR731068
7. 7. N. J. FINE and H. S. WILF, Uniqueness Theorem for Periodic functions, Proc. Am. Math. Soc., 1965, 16, pp. 109-114. Zbl0131.30203MR174934
8. 8. G. HIGMAN, Ordering by divisibility in abstract algebras, Proc. London Math. Soc., 1952, 2, pp. 326-336. Zbl0047.03402MR49867
9. 9. KRUSKAL, Well-quasi ordering, The Tree Theorem, and Vazsonyi's conjecture, Trans. Amer. Math. Soc., 1960, 95, pp. 210-225. Zbl0158.27002MR111704
10. 10. KRUSKAL, The theory of well-quasi ordering: a frequently discovered concept, J. Comb. Theory Ser., 1972, A 13 (3), pp. 297-305. Zbl0244.06002MR306057
11. 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. 12. G. KUCHEROV and M. RUSINOVITCH, Complexity of Testing Ground Reducibility for Linear Word Rewriting Systems with Variables, preprint. 
13. 13. LOTHAIRE, Combinatorics on words, chapter 1, Add.-Wesley, by D. PERRIN, 1983. Zbl0514.20045MR675953
14. 14. ld, chapter 6, by J. SAKAROVITCH. 
15. 15. E. OCHMANSKI, Inevitability in concurrent Systems, IPL 25, 1987, pp. 221-225. Zbl0653.68011MR896138
16. 16. L. PUEL, Using unavoidable sets of trees to generalize Kruskal's theorem, J.S.C., 1989, Vol. 8, No. 4, pp. 335-382. Zbl0676.06003MR1021611
17. 17. L. ROSAZ, Inventories of unavoidable languages and the word-extension conjecture, to appear in Theoretical Computer Science. Zbl0902.68099MR1625403
18. 18. L. ROSAZ, Unavoidable languages, Mémoire de thèse, LITP Report. 
19. 19. M. P. SCHUTZENBERGER, On the synchronizing properties of certain prefix codes, Information and Control, 1964, 7, pp. 23-36. Zbl0122.15004MR199049