Maximal unbordered factors of random strings

Patrick Hagge Cording; Mathias Bæk Tejs Knudsen

doi:10.1007/978-3-319-46049-9_9

Maximal unbordered factors of random strings

Patrick Hagge Cording
, Mathias Bæk Tejs Knudsen

Department of Applied Mathematics and Computer Science

University of Copenhagen

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Abstract

A border of a string is a non-empty prefix of the string that is also a suffix of the string, and a string is unbordered if it has no border. Loptev, Kucherov, and Starikovskaya [CPM 2015] conjectured the following: If we pick a string of length n from a fixed alphabet uniformly at random, then the expected length of the maximal unbordered factor is n − O(1). We prove that this conjecture is true by proving that the expected value is in fact n − Θ(σ−1), where σ is the size of the alphabet. We discuss some of the consequences of this theorem.

Original language	English
Title of host publication	Proceedings of the 23rd International Symposium String Processing and Information Retrieval (SPIRE 2016)
Editors	Shunsuke Inenaga, Kunihiko Sadakane, Tetsuya Sakai
Publisher	Springer
Publication date	2016
Pages	93-96
ISBN (Print)	978-3-319-46048-2
ISBN (Electronic)	978-3-319-46049-9
DOIs	https://doi.org/10.1007/978-3-319-46049-9_9
Publication status	Published - 2016
Event	23rd International Symposium on String Processing and Information Retrieval - Beppu, Japan Duration: 18 Oct 2016 → 20 Oct 2016 Conference number: 23 https://sites.google.com/site/spire2016jp/

Conference

Conference	23rd International Symposium on String Processing and Information Retrieval
Number	23
Country/Territory	Japan
City	Beppu
Period	18/10/2016 → 20/10/2016
Internet address	https://sites.google.com/site/spire2016jp/

Series	Lecture Notes in Computer Science
Volume	9954
ISSN	0302-9743

Access to Document

10.1007/978-3-319-46049-9_9

https://arxiv.org/pdf/1704.04472.pdf

OpenUrl availability

Check availability in DTU Findit

Cite this

@inproceedings{d67afd93990c4d2ea6906694e724fbb1,

title = "Maximal unbordered factors of random strings",

abstract = "A border of a string is a non-empty prefix of the string that is also a suffix of the string, and a string is unbordered if it has no border. Loptev, Kucherov, and Starikovskaya [CPM 2015] conjectured the following: If we pick a string of length n from a fixed alphabet uniformly at random, then the expected length of the maximal unbordered factor is n − O(1). We prove that this conjecture is true by proving that the expected value is in fact n − Θ(σ−1), where σ is the size of the alphabet. We discuss some of the consequences of this theorem.",

author = "Cording, \{Patrick Hagge\} and Knudsen, \{Mathias B{\ae}k Tejs\}",

year = "2016",

doi = "10.1007/978-3-319-46049-9\_9",

language = "English",

isbn = " 978-3-319-46048-2",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "93--96",

editor = "Inenaga, \{Shunsuke \} and Sadakane, \{Kunihiko \} and Sakai, \{Tetsuya \}",

booktitle = "Proceedings of the 23rd International Symposium String Processing and Information Retrieval (SPIRE 2016)",

note = "23rd International Symposium on String Processing and Information Retrieval, SPIRE 2016 ; Conference date: 18-10-2016 Through 20-10-2016",

url = "https://sites.google.com/site/spire2016jp/",

}

Cording, PH & Knudsen, MBT 2016, Maximal unbordered factors of random strings. in S Inenaga, K Sadakane & T Sakai (eds), Proceedings of the 23rd International Symposium String Processing and Information Retrieval (SPIRE 2016). Springer, Lecture Notes in Computer Science, vol. 9954, pp. 93-96, 23rd International Symposium on String Processing and Information Retrieval, Beppu, Japan, 18/10/2016. https://doi.org/10.1007/978-3-319-46049-9_9

Maximal unbordered factors of random strings. / Cording, Patrick Hagge; Knudsen, Mathias Bæk Tejs.
Proceedings of the 23rd International Symposium String Processing and Information Retrieval (SPIRE 2016). ed. / Shunsuke Inenaga; Kunihiko Sadakane; Tetsuya Sakai. Springer, 2016. p. 93-96 (Lecture Notes in Computer Science, Vol. 9954).

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

TY - GEN

T1 - Maximal unbordered factors of random strings

AU - Cording, Patrick Hagge

AU - Knudsen, Mathias Bæk Tejs

N1 - Conference code: 23

PY - 2016

Y1 - 2016

N2 - A border of a string is a non-empty prefix of the string that is also a suffix of the string, and a string is unbordered if it has no border. Loptev, Kucherov, and Starikovskaya [CPM 2015] conjectured the following: If we pick a string of length n from a fixed alphabet uniformly at random, then the expected length of the maximal unbordered factor is n − O(1). We prove that this conjecture is true by proving that the expected value is in fact n − Θ(σ−1), where σ is the size of the alphabet. We discuss some of the consequences of this theorem.

AB - A border of a string is a non-empty prefix of the string that is also a suffix of the string, and a string is unbordered if it has no border. Loptev, Kucherov, and Starikovskaya [CPM 2015] conjectured the following: If we pick a string of length n from a fixed alphabet uniformly at random, then the expected length of the maximal unbordered factor is n − O(1). We prove that this conjecture is true by proving that the expected value is in fact n − Θ(σ−1), where σ is the size of the alphabet. We discuss some of the consequences of this theorem.

U2 - 10.1007/978-3-319-46049-9_9

DO - 10.1007/978-3-319-46049-9_9

M3 - Article in proceedings

SN - 978-3-319-46048-2

T3 - Lecture Notes in Computer Science

SP - 93

EP - 96

BT - Proceedings of the 23rd International Symposium String Processing and Information Retrieval (SPIRE 2016)

A2 - Inenaga, Shunsuke

A2 - Sadakane, Kunihiko

A2 - Sakai, Tetsuya

PB - Springer

T2 - 23rd International Symposium on String Processing and Information Retrieval

Y2 - 18 October 2016 through 20 October 2016

ER -

Maximal unbordered factors of random strings

Abstract

Conference

Access to Document

OpenUrl availability

Fingerprint

Cite this