Studying Word Equations by a Method of Weighted Frequencies

• Autorzy: Saarela A.

Identyfikatory

DOI

10.3233/FI-2018-1722

• Konferencja: RuFiDiM Conference, Russian-Finnish Symposium in Discrete Mathematics (5; 16-19.05. 2017; Turku; Finland)
• Języki publikacji: EN

Abstrakty

EN

We briefly survey some results and open problems on word equations, especially on those equations where the right-hand side is a power of a variable. We discuss a method that was recently used to prove one of the results, and we prove improved versions of some lemmas that are related to the method and can be used as tools when studying word equations. We use the method and the tools to give new, simple proofs for several old results.

Słowa kluczowe

EN

free groups; combinatorics; integers; compact spaces; mathematical analysis

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2018
• Tom: Vol. 162, nr 2/3
• Strony: 223--235
• Opis fizyczny: Bibliogr. 20 poz., rys., wykr.

Twórcy

autor

Saarela A.

• Department of Mathematics and Statistics, University of Turku, 20014 Turku, Finland

Bibliografia

• [1] Albert MH, Lawrence J. A proof of Ehrenfeucht’s conjecture, Theoret. Comput. Sci., 1985;41(1):121-123.
• [2] Barbin-Le Rest E, Le Rest M. Sur la combinatoire des codes à deux mots, Theoret. Comput. Sci., 1985;41(1):61-80. URL https://doi.org/10.1016/0304-3975(85)90060-X.
• [3] Culik IIK, Karhumäki J. Systems of equations over a free monoid and Ehrenfeucht’s conjecture, Discrete Math., 1983:43(2-3):139-153. doi:10.1016/0012-365X(83)90152-8.
• [4] Dömösi P, Horváth G, Vuillon L. On the Shyr-Yu theorem, Theoret. Comput. Sci., 2009;410(47-49):4874-4877. URL https://doi.org/10.1016/j.tcs.2009.06.039.
• [5] Guba VS. Equivalence of infinite systems of equations in free groups and semigroups to finite subsystems, Mat. Zametki, 1986;40(3):321-324.
• [6] Hakala I, Kortelainen J. On the system of word equations [formula] in a free monoid, Acta Inform., 1997;34(3):217-230. doi:10.1007/s002360050081.
• [7] Harju T, Nowotka D. The equation xi = yjzk in a free semigroup, Semigroup Forum, 2004;68(3):488-490. doi:10.1007/s00233-003-0028-6.
• [8] Harju T, Nowotka D. On the equation [formula] in a free semigroup, Theoret. Comput. Sci., 2005;330(1):117-121. URL https://doi.org/10.1016/j.tcs.2004.09.012.
• [9] Holub Š. Local and global cyclicity in free semigroups, Theoret. Comput. Sci., 2001;262(1-2):25-36. URL https://doi.org/10.1016/S0304-3975(00)00156-0.
• [10] Holub, Š, Kortelainen J. On systems of word equations with simple loop sets, Theoret. Comput. Sci., 2007;380(3):363-372. doi:10.1016/j.tcs.2007.03.026.
• [11] Karhumäki J, Plandowski W. On the defect effect of many identities in free semigroups, in: Mathematical aspects of natural and formal languages (G. Paun, Ed.), World Scientific, 1994, 225-232. ISBN:9-8102-1914-8.
• [12] Kortelainen J. On the system of word equations [formula] in a free monoid, J. Autom. Lang. Comb., 1998;3(1):43-57.
• [13] Lothaire M. Algebraic Combinatorics on Words, Cambridge University Press, 2002. ISBN: 0521812208.
• [14] Lyndon RC, Schützenberger M-P. The equation aM = bNcP in a free group, Michigan Math. J., 1962; 9(4):289-298.
• [15] Nowotka D, Saarela A. One-variable word equations and three-variable constant-free word equations, Internat. J. Found. Comput. Sci., To appear.
• [16] Plandowski W. Test sets for large families of languages, Proceedings of the 7th DLT, 2710, Springer, 2003. doi:10.1007/3-540-45007-6_6.
• [17] Saarela A. Systems of word equations, polynomials and linear algebra: A new approach, European J. Combin., 2015;47:1-14. URL https://doi.org/10.1016/j.ejc.2015.01.005.
• [18] Saarela A. Word equations where a power equals a product of powers, Proceedings of the 34th STACS, 66, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017.
• [19] Shyr HJ, Yu S-S. Non-primitive words in the language p+q+, Soochow J. Math.,1994;20(4):535-546.
• [20] Spehner J-C. Quelques problémes d’extension, de conjugaison et de présentation des sous-monoïdes d’un monoïde libre, Ph.D. Thesis, Univ. Paris, 1976.