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

^*Corresponding author af dette arbejde

Datalogisk Institut

2 Citationer (Scopus)

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−Θ(σ⁻¹), where σ is the size of the alphabet. We discuss some of the consequences of this theorem.

Originalsprog	Engelsk
Titel	String Processing and Information Retrieval : 23rd International Symposium, SPIRE 2016, Beppu, Japan, October 18-20, 2016, Proceedings
Redaktører	Shunsuke Inenaga, Kunihiko Sadakane, Tetsuya Sakai
Antal sider	4
Forlag	Springer
Publikationsdato	2016
Sider	93-96
ISBN (Trykt)	978-3-319-46048-2
ISBN (Elektronisk)	978-3-319-46049-9
DOI	https://doi.org/10.1007/978-3-319-46049-9_9
Status	Udgivet - 2016
Begivenhed	23rd International Symposium on String Processing and Information Retrieval - Beppu, Japan Varighed: 8 okt. 2016 → 20 okt. 2016 Konferencens nummer: 23

Konference

Konference	23rd International Symposium on String Processing and Information Retrieval
Nummer	23
Land/Område	Japan
By	Beppu
Periode	08/10/2016 → 20/10/2016

Navn	Lecture notes in computer science
Vol/bind	9954
ISSN	0302-9743

Adgang til dokumentet

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

Andre filer og links

Link to publication in Scopus

Citationsformater

Cording, P. H., & Knudsen, M. B. T. (2016). Maximal unbordered factors of random strings. I S. Inenaga, K. Sadakane, & T. Sakai (red.), String Processing and Information Retrieval: 23rd International Symposium, SPIRE 2016, Beppu, Japan, October 18-20, 2016, Proceedings (s. 93-96). Springer. Lecture notes in computer science Bind 9954 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.

String Processing and Information Retrieval: 23rd International Symposium, SPIRE 2016, Beppu, Japan, October 18-20, 2016, Proceedings. red. / Shunsuke Inenaga; Kunihiko Sadakane; Tetsuya Sakai. Springer, 2016. s. 93-96 (Lecture notes in computer science, Bind 9954).

Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › peer review

Cording, PH & Knudsen, MBT 2016, Maximal unbordered factors of random strings. i S Inenaga, K Sadakane & T Sakai (red), String Processing and Information Retrieval: 23rd International Symposium, SPIRE 2016, Beppu, Japan, October 18-20, 2016, Proceedings. Springer, Lecture notes in computer science, bind 9954, s. 93-96, 23rd International Symposium on String Processing and Information Retrieval, Beppu, Japan, 08/10/2016. https://doi.org/10.1007/978-3-319-46049-9_9

Cording, Patrick Hagge ; Knudsen, Mathias Bæk Tejs. / Maximal unbordered factors of random strings. String Processing and Information Retrieval: 23rd International Symposium, SPIRE 2016, Beppu, Japan, October 18-20, 2016, Proceedings. red. / Shunsuke Inenaga ; Kunihiko Sadakane ; Tetsuya Sakai. Springer, 2016. s. 93-96 (Lecture notes in computer science, Bind 9954).

@inproceedings{44e57290e1e546d29d458737eff66a7e,

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 = "Shunsuke Inenaga and Kunihiko Sadakane and Tetsuya Sakai",

booktitle = "String Processing and Information Retrieval",

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

}

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.

UR - http://www.scopus.com/inward/record.url?scp=84989815012&partnerID=8YFLogxK

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

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

M3 - Article in proceedings

AN - SCOPUS:84989815012

SN - 978-3-319-46048-2

T3 - Lecture notes in computer science

SP - 93

EP - 96

BT - String Processing and Information Retrieval

A2 - Inenaga, Shunsuke

A2 - Sadakane, Kunihiko

A2 - Sakai, Tetsuya

PB - Springer

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

Y2 - 8 October 2016 through 20 October 2016

ER -

Maximal unbordered factors of random strings

Abstract

Konference

Adgang til dokumentet

Andre filer og links

Fingeraftryk

Citationsformater