Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Saarela, Aleksi http://www.dagstuhl.de/lipics License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-69793
URL:

Word Equations Where a Power Equals a Product of Powers

pdf-format:


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.

BibTeX - Entry

@InProceedings{saarela:LIPIcs:2017:6979,
  author =	{Aleksi Saarela},
  title =	{{Word Equations Where a Power Equals a Product of Powers}},
  booktitle =	{34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
  pages =	{55:1--55:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-028-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{66},
  editor =	{Heribert Vollmer and Brigitte Vallée},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/6979},
  URN =		{urn:nbn:de:0030-drops-69793},
  doi =		{10.4230/LIPIcs.STACS.2017.55},
  annote =	{Keywords: Combinatorics on words, Word equations}
}

Keywords: Combinatorics on words, Word equations
Seminar: 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)
Issue date: 2017
Date of publication: 2017


DROPS-Home | Fulltext Search | Imprint Published by LZI