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.CPM.2017.21
URN: urn:nbn:de:0030-drops-73309
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7330/
Go to the corresponding LIPIcs Volume Portal

Duchon, Philippe ; Nicaud, Cyril ; Pivoteau, Carine

Gapped Pattern Statistics

pdf-format:
LIPIcs-CPM-2017-21.pdf (0.5 MB)

Abstract

We give a probabilistic analysis of parameters related to alpha-gapped repeats and palindromes in random words, under both uniform and memoryless distributions (where letters have different probabilities, but are drawn independently). More precisely, we study the expected number of maximal alpha-gapped patterns, as well as the expected length of the longest alpha-gapped pattern in a random word.

BibTeX - Entry

@InProceedings{duchon_et_al:LIPIcs:2017:7330,
  author =	{Philippe Duchon and Cyril Nicaud and Carine Pivoteau},
  title =	{{Gapped Pattern Statistics}},
  booktitle =	{28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017)},
  pages =	{21:1--21:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-039-2},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{78},
  editor =	{Juha K{\"a}rkk{\"a}inen and Jakub Radoszewski and Wojciech Rytter},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7330},
  URN =		{urn:nbn:de:0030-drops-73309},
  doi =		{10.4230/LIPIcs.CPM.2017.21},
  annote =	{Keywords: combinatorics on words, alpha-gapped repeats, random words, memoryless sources, analytic combinatorics}
}

Keywords: combinatorics on words, alpha-gapped repeats, random words, memoryless sources, analytic combinatorics
Collection: 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017)
Issue Date: 2017
Date of publication: 30.06.2017

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