License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2016.81
URN: urn:nbn:de:0030-drops-64892
URL: http://drops.dagstuhl.de/opus/volltexte/2016/6489/
Go to the corresponding LIPIcs Volume Portal


Rosenfeld, Matthieu

Every Binary Pattern of Length Greater Than 14 Is Abelian-2-Avoidable

pdf-format:
LIPIcs-MFCS-2016-81.pdf (0.4 MB)


Abstract

We show that every binary pattern of length greater than 14 is abelian-2-avoidable. The best known upper bound on the length of abelian-2-unavoidable binary pattern was 118, and the best known lower bound is 7. We designed an algorithm to decide, under some reasonable assumptions, if a morphic word avoids a pattern in the abelian sense. This algorithm is then used to show that some binary patterns are abelian-2-avoidable. We finally use this list of abelian-2-avoidable pattern to show our result. We also discuss the avoidability of binary patterns on 3 and 4 letters.

BibTeX - Entry

@InProceedings{rosenfeld:LIPIcs:2016:6489,
  author =	{Matthieu Rosenfeld},
  title =	{{Every Binary Pattern of Length Greater Than 14 Is Abelian-2-Avoidable}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{81:1--81:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Piotr Faliszewski and Anca Muscholl and Rolf Niedermeier},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6489},
  URN =		{urn:nbn:de:0030-drops-64892},
  doi =		{10.4230/LIPIcs.MFCS.2016.81},
  annote =	{Keywords: combinatorics on words, pattern avoidance, abelian repetitions}
}

Keywords: combinatorics on words, pattern avoidance, abelian repetitions
Seminar: 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)
Issue Date: 2016
Date of publication: 19.08.2016


DROPS-Home | Fulltext Search | Imprint Published by LZI