Finite degrees of ambiguity in pattern languages
Mateescu, A. ; Salomaa, A.
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 28 (1994), p. 233-253 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1994-01-01
@article{ITA_1994__28_3-4_233_0,
     author = {Mateescu, A. and Salomaa, A.},
     title = {Finite degrees of ambiguity in pattern languages},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {28},
     year = {1994},
     pages = {233-253},
     mrnumber = {1282446},
     zbl = {0883.68076},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1994__28_3-4_233_0}
}

Mateescu, A.; Salomaa, A. Finite degrees of ambiguity in pattern languages. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 28 (1994) pp. 233-253. http://gdmltest.u-ga.fr/item/ITA_1994__28_3-4_233_0/

1. D. Angluin, Finding patterns common to a set of strings, Journal of Computer and System Sciences, 1980, 21, pp. 46-62. | MR 589803 | Zbl 0454.68108

2. J. Bean, A. Ehrenfeucht, and G. Mcnulty, Avoidable patterns in strings of symbols, Pacific Journal of Mathematics, 1979, 85, pp. 261-294. | MR 574919 | Zbl 0428.05001

3. J. Cassaigne, Unavoidable binary patterns, Acta Informatica, 1993, 30, pp. 385-395. | MR 1227889 | Zbl 0790.68096

4. K. Culik Ii and J. Karhumäki, Systems of equations over a free monoid and Ehrenfeucht's conjecture, Discrete Mathematics, 1983, 43, pp. 139-153. | MR 685623 | Zbl 0528.68057

5. T. Jiang, E. Kinber, A. Salomaa, K. Salomaa and S. Yu, Pattern languages with and without erasing, to appear in International Journal of Computer Mathematics. | Zbl 0939.68690

6. T. Jiang, A. Salomaa, K. Salomaa and S. Yu, Inclusion is undecidable for pattern languages, ICALP-93 Proceedings, Springer Lecture Notes in Computer Science, 1993, 700, pp. 301-312.

7. V. Keränen, Abelian squares can be avoided on four letters, Springer Lecture Notes in Computer Science, 1992, 623, pp. 41-52. | MR 1250629

8. G. Kucherov, M. Rusinowitch, On ground reducibility problem for word rewriting Systems with variables, Centre de Recherche en Informatique de Nancy, Report CRIN 93-R-012.

9. G. S. Makanin, The problem of solvability of equations in a free semigroup (in Russian), Matematiceskij Sbornik, 1977, 103, 145, pp. 148-236. | MR 470107 | Zbl 0371.20047

10. A. Salomaa, Formal Languages, Academic Press, 1973. | MR 438755 | Zbl 0262.68025

11. A. Thue, Über unendliche Zeichenreihen, Norske Vid. Selsk. Skr., I Mat. Nat. Kl., Kristiania, 1906, 7, pp. 1-22. | JFM 39.0283.01