License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2017.55
URN: urn:nbn:de:0030-drops-69793
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/6979/
Go to the corresponding LIPIcs Volume Portal

Saarela, Aleksi

Word Equations Where a Power Equals a Product of Powers

pdf-format:
LIPIcs-STACS-2017-55.pdf (0.4 MB)

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 ValleĢ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
Collection: 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)
Issue Date: 2017
Date of publication: 06.03.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI