LIPIcs.CPM.2017.21.pdf
- Filesize: 0.48 MB
- 12 pages
Document
Gapped Pattern Statistics
Authors
-
Part of:
Volume:
28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Annual Symposium on Combinatorial Pattern Matching (CPM) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2017-06-30
Cite As Get BibTex
Philippe Duchon, Cyril Nicaud, and Carine Pivoteau. Gapped Pattern Statistics. In 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 78, pp. 21:1-21:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.CPM.2017.21
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.
Subject Classification
Keywords
- combinatorics on words
- alpha-gapped repeats
- random words
- memoryless sources
- analytic combinatorics
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Gerth Stølting Brodal, Rune B. Lyngsø, Christian N. S. Pedersen, and Jens Stoye. Finding maximal pairs with bounded gap. In Maxime Crochemore and Mike Paterson, editors, Proceedings of the 10th Annual Symposium on Combinatorial Pattern Matching (CPM 1999), volume 1645 of LNCS, pages 134-149. Springer, 1999. URL: http://dx.doi.org/10.1007/3-540-48452-3_11.
- Maxime Crochemore, Roman Kolpakov, and Gregory Kucherov. Optimal bounds for computing α-gapped repeats. In Adrian-Horia Dediu, Jan Janousek, Carlos Martín-Vide, and Bianca Truthe, editors, Proceedings of the 10th International Conference on Language and Automata Theory and Applications (LATA 2016), volume 9618 of LNCS, pages 245-255. Springer, 2016. URL: http://dx.doi.org/10.1007/978-3-319-30000-9_19.
-
Maxime Crochemore and Wojciech Rytter. Text Algorithms. Oxford University Press, 1994.
- Marius Dumitran and Florin Manea. Longest gapped repeats and palindromes. In Giuseppe F. Italiano, Giovanni Pighizzini, and Donald Sannella, editors, Proceedings of the 40th International Symposium on Mathematical Foundations of Computer Science (MFCS 2015), volume 9234 of LNCS, pages 205-217. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-662-48057-1_16.
- Philippe Flajolet and Robert Sedgewick. Analytic Combinatorics. Cambridge University Press, 2009. URL: http://dx.doi.org/10.1017/CBO9780511801655.
- Paweł Gawrychowski, Tomohiro I, Shunsuke Inenaga, Dominik Köppl, and Florin Manea. Efficiently finding all maximal α-gapped repeats. In Nicolas Ollinger and Heribert Vollmer, editors, Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016), volume 47 of LIPIcs, pages 39:1-39:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2016.39.
- Paweł Gawrychowski and Florin Manea. Longest α-gapped repeat and palindrome. In Adrian Kosowski and Igor Walukiewicz, editors, Proceedings of the 20th International Symposium on Fundamentals of Computation Theory (FCT 2015), volume 9210 of LNCS, pages 27-40. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-319-22177-9_3.
- Amy Glen and Jamie Simpson. The total run length of a word. Theor. Comput. Sci., 501:41-48, 2013. URL: http://dx.doi.org/10.1016/j.tcs.2013.06.004.
- Leonidas J. Guibas and Andrew M. Odlyzko. String overlaps, pattern matching, and nontransitive games. J. Comb. Theory, Ser. A, 30(2):183-208, 1981. URL: http://dx.doi.org/10.1016/0097-3165(81)90005-4.
- Roman Kolpakov and Gregory Kucherov. Searching for gapped palindromes. Theor. Comput. Sci., 410(51):5365-5373, 2009. URL: http://dx.doi.org/10.1016/j.tcs.2009.09.013.
- Roman Kolpakov, Mikhail Podolskiy, Mikhail Posypkin, and Nickolay Khrapov. Searching of gapped repeats and subrepetitions in a word. In Alexander S. Kulikov, Sergei O. Kuznetsov, and Pavel A. Pevzner, editors, Proceedings of the 25th Annual Symposium on Combinatorial Pattern Matching (CPM 2014), volume 8486 of LNCS, pages 212-221. Springer, 2014. URL: http://dx.doi.org/10.1007/978-3-319-07566-2_22.
- Roman M. Kolpakov and Gregory Kucherov. Finding repeats with fixed gap. In Pablo de la Fuente, editor, Proceedings of the 7th International Symposium on String Processing and Information Retrieval (SPIRE 2000), pages 162-168. IEEE Computer Society, 2000. URL: http://dx.doi.org/10.1109/SPIRE.2000.878192.
- Cyril Nicaud. Estimating statistics on words using ambiguous descriptions. In Roberto Grossi and Moshe Lewenstein, editors, Proceedings of the 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016), volume 54 of LIPIcs, pages 9:1-9:12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.CPM.2016.9.
- Simon J. Puglisi and Jamie Simpson. The expected number of runs in a word. Australas. J. Comb., 42:45-54, 2008. URL: https://ajc.maths.uq.edu.au/pdf/42/ajc_v42_p045.pdf.
- Mikhail Rubinchik and Arseny M. Shur. The number of distinct subpalindromes in random words. Fundam. Inform., 145(3):371-384, 2016. URL: http://dx.doi.org/10.3233/FI-2016-1366.
- Arseny M. Shur. Growth properties of power-free languages. Comput. Sci. Rev., 6(5-6):187-208, 2012. URL: http://dx.doi.org/10.1016/j.cosrev.2012.09.001.
- Yuka Tanimura, Yuta Fujishige, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. A faster algorithm for computing maximal α-gapped repeats in a string. In Costas S. Iliopoulos, Simon J. Puglisi, and Emine Yilmaz, editors, Proceedings of the 22nd International Symposium on String Processing and Information Retrieval (SPIRE 2015), volume 9309 of LNCS, pages 124-136. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-319-23826-5_13.