Unavoidable languages, cuts and innocent sets of words
Rosaz, L.
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 29 (1995), p. 339-382 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1995-01-01
@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},
     volume = {29},
     year = {1995},
     pages = {339-382},
     mrnumber = {1360665},
     zbl = {0838.68068},
     language = {en},
     url = {http://dml.mathdoc.fr/item/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) pp. 339-382. http://gdmltest.u-ga.fr/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 371172 | Zbl 0301.68048

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 574919 | Zbl 0428.05001

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 819242 | Zbl 0571.68056

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

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 707587 | Zbl 0506.68057

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

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

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

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

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

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 675953 | Zbl 0514.20045

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

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

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 1021611 | Zbl 0676.06003

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

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 199049 | Zbl 0122.15004