Word Equations Where a Power Equals a Product of Powers
Document Open Access Logo

Word Equations Where a Power Equals a Product of Powers

Author Aleksi Saarela

PDF
Thumbnail PDF

File

LIPIcs.STACS.2017.55.pdf
  • Filesize: 438 kB
  • 9 pages

Document Identifiers

Author Details

Aleksi Saarela

Cite As Get BibTex

Aleksi Saarela. Word Equations Where a Power Equals a Product of Powers. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 55:1-55:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.STACS.2017.55

Abstract

We solve a long-standing open problem on word equations by proving that if the words x_0, ..., x_n satisfy the equation x_0^k = x_1^k ... x_n^k for three positive values of k, then the words commute. One of our methods is to assign numerical values for the letters, and then study the sums of the letters of words and their prefixes. We also give a geometric interpretation of our methods.

Subject Classification

Keywords
  • Combinatorics on words
  • Word equations

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. K. I. Appel and F. M. Djorup. On the equation z₁ⁿz₂ⁿ⋯ z_k ⁿ = yⁿ in a free semigroup. Trans. Amer. Math. Soc., 134:461-470, 1968. Google Scholar
  2. Srečko Brlek. Interactions between digital geometry and combinatorics on words. In Proceedings of the 8th WORDS, volume 63 of EPTCS, pages 1-12, 2011. URL: http://dx.doi.org/10.4204/EPTCS.63.1.
  3. Emmanuel Filiot, Olivier Gauwin, Pierre-Alain Reynier, and Frédéric Servais. Streamability of nested word transductions. In Proceedings of the 31st FSTTCS, volume 13 of LIPIcs, pages 312-324. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2011. Google Scholar
  4. Ismo Hakala and Juha Kortelainen. On the system of word equations xⁱ₁xⁱ₂⋯ xⁱ_m = yⁱ₁yⁱ₂⋯ yⁱ_n (i = 1,2,⋯) in a free monoid. Acta Inform., 34(3):217-230, 1997. URL: http://dx.doi.org/10.1007/s002360050081.
  5. Tero Harju and Dirk Nowotka. On the equation x^k = z^k₁₁ z^k₂₂⋯ z^k_n_n in a free semigroup. Theoret. Comput. Sci., 330(1):117-121, 2005. URL: http://dx.doi.org/10.1016/j.tcs.2004.09.012.
  6. Štěpán Holub. A solution of the equation (x₁²⋯ x_n²)³ = (x₁³⋯ x_n³)². In Contributions to general algebra, 11 (Olomouc/Velké Karlovice, 1998), pages 105-111. Heyn, 1999. Google Scholar
  7. Štěpán Holub. Local and global cyclicity in free semigroups. Theoret. Comput. Sci., 262(1-2):25-36, 2001. URL: http://dx.doi.org/10.1016/S0304-3975(00)00156-0.
  8. Štěpán Holub and Juha Kortelainen. On systems of word equations with simple loop sets. Theoret. Comput. Sci., 380(3):363-372, 2007. URL: http://dx.doi.org/10.1016/j.tcs.2007.03.026.
  9. Juhani Karhumäki and Wojciech Plandowski. On the defect effect of many identities in free semigroups. In Gheorghe Paun, editor, Mathematical aspects of natural and formal languages, pages 225-232. World Scientific, 1994. Google Scholar
  10. Juha Kortelainen. On the system of word equations x₀u₁^ix₁u₂^ix₂⋯ u_m^ix_m = y₀v₁^iy₁v₂^iy₂⋯ v_n^iy_n (i = 0,1,2,⋯) in a free monoid. J. Autom. Lang. Comb., 3(1):43-57, 1998. Google Scholar
  11. André Lentin. Sur l'équation a^M = b^Nc^Pd^Q dans un monoïde libre. C. R. Acad. Sci. Paris, 260:3242-3244, 1965. Google Scholar
  12. M. Lothaire. Combinatorics on Words. Addison-Wesley, 1983. Google Scholar
  13. Roger C. Lyndon and Marcel-Paul Schützenberger. The equation a^M = b^Nc^P in a free group. Michigan Math. J., 9(4):289-298, 1962. URL: http://dx.doi.org/10.1307/mmj/1028998766.
  14. Jarkko Peltomäki and Markus Whiteland. A square root map on Sturmian words (extended abstract). In Proceedings of the 10th WORDS, volume 9304 of LNCS, pages 197-209. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-319-23660-5_17.
  15. Wojciech Plandowski. Test sets for large families of languages. In Proceedings of the 7th DLT, volume 2710 of LNCS, pages 75-94. Springer, 2003. URL: http://dx.doi.org/10.1007/3-540-45007-6_6.
  16. Aleksi Saarela. Systems of word equations, polynomials and linear algebra: A new approach. European J. Combin., 47:1-14, 2015. URL: http://dx.doi.org/10.1016/j.ejc.2015.01.005.
  17. Huei Jan Shyr and Shyr-Shen Yu. Non-primitive words in the language p^+q^+. Soochow J. Math., 20(4):535-546, 1994. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact