Regular PapersNo Access

ON NON-PERIODIC SOLUTIONS OF INDEPENDENT SYSTEMS OF WORD EQUATIONS OVER THREE UNKNOWNS

ELENA CZEIZLER

Department of Mathematics, University of Turku and Turku Centre for Computer Science, Turku 20520, Finland

Search for more papers by this author

and

JUHANI KARHUMÄKI

Department of Mathematics, University of Turku and Turku Centre for Computer Science, Turku 20014, Finland

Search for more papers by this author

https://doi.org/10.1142/S0129054107005030Cited by:11 (Source: Crossref)

Abstract

We investigate the open question asking whether there exist independent systems of three equations over three unknowns admitting non-periodic solutions, formulated in 1983 by Culik II and Karhumäki. In particular, we give a negative answer to this question for a large class of systems. More specifically, the question remains open only for a well specified class of systems. We also investigate systems of two equations over three unknowns for which we give necessary and sufficient conditions for admitting at most quasi-periodic solutions, i.e., solutions where the images of two unknowns are powers of a common word. In doing so, we also give a number of examples showing that these conditions represent a boundary point between systems admitting purely non-periodic solutions and those admitting at most quasi-periodic ones.

References

M. H. Albert and J. Lawrence, Theoret. Comput. Sci. 41, 121 (1985), DOI: 10.1016/0304-3975(85)90066-0. Crossref, Web of Science, Google Scholar
L. G. Budkina and Al. A. Markov, Mathematical notes of the Academy of Science of the USSR 14, 711 (1974), DOI: 10.1007/BF01147120. Crossref, Google Scholar
C. Choffrut and J. Karhumäki, Handbook of Formal Languages 1, eds. G. Rozenberg and A. Salomaa (Springer-Verlag, Berlin, 1997) pp. 329–438. Crossref, Google Scholar
K. Culik II and J. Karhumäki, Discrete Math. 43(2–3), 139 (1983), DOI: 10.1016/0012-365X(83)90152-8. Crossref, Web of Science, Google Scholar
E. Czeizler, Theoret. Comput. Sci. 345(2–3), 296 (2005), DOI: 10.1016/j.tcs.2005.07.012. Crossref, Web of Science, Google Scholar
E. Czeizler , Multiple Constraints on Three and Four Words , Proceedings of CANT . Google Scholar
V. S. Guba, Mat. Zametki 40(3), 321 (1986). Google Scholar
T. Harju and J. Karhumäki, Semigroup Forum 33(2), 199 (1986), DOI: 10.1007/BF02573193. Crossref, Web of Science, Google Scholar
T. Harju and D. Nowotka, Theoret. Comput. Sci. 307(1), 139 (2003), DOI: 10.1016/S0304-3975(03)00098-7. Crossref, Web of Science, Google Scholar
Ju. I. Hmelevskiĭ , Equations in free semigroups ( American Mathematical Society , Providence, R.I. , 1976 ) . Google Scholar
J. Karhumäki, F. Mignosi and W. Plandowski, J. ACM 47(3), 483 (2000). Crossref, Web of Science, Google Scholar
J. Karhumäki and W. Plandowski, Mathematical Aspects of Natural and Formal Languages, ed. Gh. Paun (World-Scientific, 1994) pp. 225–233. Link, Google Scholar
J. Karhumäki and W. Plandowski, Theoret. Comput. Sci. 168(1), 105 (1996). Crossref, Web of Science, Google Scholar
A. Lentin, Automata, languages and programming, ed. M. Nivat (1972) pp. 67–85. Google Scholar
F. W. Levi, Bull. Calcutta Math. Soc. 36, 141 (1944). Google Scholar
G. S. Makanin, Math USSR Sbornik 32, 129 (1977), DOI: 10.1070/SM1977v032n02ABEH002376. Crossref, Web of Science, Google Scholar
E. Petre, Mathematical foundations of computer science 2004, Lecture Notes in Comput. Sci. 3153, eds. J. Fiala, V. Koubek and J. Kratochvíl (Springer, Berlin, 2004) pp. 807–817. Crossref, Google Scholar
W. Plandowski, J. ACM 51(3), 483 (2004), DOI: 10.1145/990308.990312. Crossref, Web of Science, Google Scholar
J.-C. Spehner, Quelques problèmes d'extension, de conjugaison et de presentation des sousmonoïdes d'un monoïde libre, Ph.D. Thesis, Université Paris VII, 1976 . Google Scholar