On extended special factors of a word

Panagiotis Charalampopoulos; Maxime Crochemore; Solon P. Pissis

doi:10.1007/978-3-030-00479-8_11

On extended special factors of a word

Panagiotis Charalampopoulos, Maxime Crochemore, Solon P. Pissis^*

^*Corresponding author for this work

Research output: Chapter in Book / Report / Conference proceeding › Conference contribution › Academic › peer-review

Abstract

An extended special factor of a word x is a factor of x whose longest infix can be extended by at least two distinct letters to the left or to the right and still occur in x. It is called extended bispecial if it can be extended in both directions and still occur in x. Let ρ(n) be the maximum number of extended bispecial factors over all words of length n. Almirantis et al. have shown that 2n - 6≤ ρ(n)≤ 3n-4 [WABI 2017]. In this article, we show that there is no constant c <3 such that ρ(n)≤cn. We then exploit the connection between extended special factors and minimal absent words to construct a data structure for computing minimal absent words of a specific length in optimal time for integer alphabets generalising a result by Fujishige et al. [MFCS 2016]. As an application of our data structure, we show how to compare two words over an integer alphabet in optimal time improving on another result by Charalampopoulos et al. [Inf. Comput. 2018].

Original language	English
Title of host publication	String Processing and Information Retrieval - 25th International Symposium, SPIRE 2018, Proceedings
Editors	Travis Gagie, Alistair Moffat, Gonzalo Navarro, Ernesto Cuadros-Vargas
Publisher	Springer Verlag
Pages	131-138
Number of pages	8
ISBN (Print)	9783030004781
DOIs	https://doi.org/10.1007/978-3-030-00479-8_11
Publication status	Published - 1 Jan 2018
Externally published	Yes
Event	25th International Symposium on String Processing and Information Retrieval, SPIRE 2018 - Lima, Peru Duration: 9 Oct 2018 → 11 Oct 2018

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	11147 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	25th International Symposium on String Processing and Information Retrieval, SPIRE 2018
Country/Territory	Peru
City	Lima
Period	9/10/18 → 11/10/18

Funding

P. Charalampopoulos—Partially supported by a Studentship from the Faculty of Natural and Mathematical Sciences at King’s College London and an A. G. Leventis Foundation Educational Grant. Acknowledgements. The authors would like to acknowledge the financial support towards travel and subsistence from the Laboratoire d’Informatique Gaspard-Monge at the UniversitéParis-Est, where part of this work has been conducted.

Funders	Funder number
A. G. Leventis Foundation
Faculty of Natural and Mathematical Sciences at King’s College London
Laboratoire d’Informatique Gaspard-Monge
A.G. Leventis Foundation

Keywords

Minimal absent words
Special factors
String algorithms

Access to Document

10.1007/978-3-030-00479-8_11

Persistent URL (handle)

Persistent link

Cite this

Charalampopoulos, P., Crochemore, M., & Pissis, S. P. (2018). On extended special factors of a word. In T. Gagie, A. Moffat, G. Navarro, & E. Cuadros-Vargas (Eds.), String Processing and Information Retrieval - 25th International Symposium, SPIRE 2018, Proceedings (pp. 131-138). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11147 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-030-00479-8_11

Charalampopoulos, Panagiotis ; Crochemore, Maxime ; Pissis, Solon P. / On extended special factors of a word. String Processing and Information Retrieval - 25th International Symposium, SPIRE 2018, Proceedings. editor / Travis Gagie ; Alistair Moffat ; Gonzalo Navarro ; Ernesto Cuadros-Vargas. Springer Verlag, 2018. pp. 131-138 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{acd7cf816e164ce1bfd9ce2944b8a6fd,

title = "On extended special factors of a word",

abstract = "An extended special factor of a word x is a factor of x whose longest infix can be extended by at least two distinct letters to the left or to the right and still occur in x. It is called extended bispecial if it can be extended in both directions and still occur in x. Let ρ(n) be the maximum number of extended bispecial factors over all words of length n. Almirantis et al. have shown that 2n - 6≤ ρ(n)≤ 3n-4 [WABI 2017]. In this article, we show that there is no constant c <3 such that ρ(n)≤cn. We then exploit the connection between extended special factors and minimal absent words to construct a data structure for computing minimal absent words of a specific length in optimal time for integer alphabets generalising a result by Fujishige et al. [MFCS 2016]. As an application of our data structure, we show how to compare two words over an integer alphabet in optimal time improving on another result by Charalampopoulos et al. [Inf. Comput. 2018].",

keywords = "Minimal absent words, Special factors, String algorithms",

author = "Panagiotis Charalampopoulos and Maxime Crochemore and Pissis, {Solon P.}",

year = "2018",

month = jan,

day = "1",

doi = "10.1007/978-3-030-00479-8_11",

language = "English",

isbn = "9783030004781",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "131--138",

editor = "Travis Gagie and Alistair Moffat and Gonzalo Navarro and Ernesto Cuadros-Vargas",

booktitle = "String Processing and Information Retrieval - 25th International Symposium, SPIRE 2018, Proceedings",

address = "Germany",

note = "25th International Symposium on String Processing and Information Retrieval, SPIRE 2018 ; Conference date: 09-10-2018 Through 11-10-2018",

}

Charalampopoulos, P, Crochemore, M & Pissis, SP 2018, On extended special factors of a word. in T Gagie, A Moffat, G Navarro & E Cuadros-Vargas (eds), String Processing and Information Retrieval - 25th International Symposium, SPIRE 2018, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11147 LNCS, Springer Verlag, pp. 131-138, 25th International Symposium on String Processing and Information Retrieval, SPIRE 2018, Lima, Peru, 9/10/18. https://doi.org/10.1007/978-3-030-00479-8_11

On extended special factors of a word. / Charalampopoulos, Panagiotis; Crochemore, Maxime; Pissis, Solon P.
String Processing and Information Retrieval - 25th International Symposium, SPIRE 2018, Proceedings. ed. / Travis Gagie; Alistair Moffat; Gonzalo Navarro; Ernesto Cuadros-Vargas. Springer Verlag, 2018. p. 131-138 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11147 LNCS).

Research output: Chapter in Book / Report / Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - On extended special factors of a word

AU - Charalampopoulos, Panagiotis

AU - Crochemore, Maxime

AU - Pissis, Solon P.

PY - 2018/1/1

Y1 - 2018/1/1

N2 - An extended special factor of a word x is a factor of x whose longest infix can be extended by at least two distinct letters to the left or to the right and still occur in x. It is called extended bispecial if it can be extended in both directions and still occur in x. Let ρ(n) be the maximum number of extended bispecial factors over all words of length n. Almirantis et al. have shown that 2n - 6≤ ρ(n)≤ 3n-4 [WABI 2017]. In this article, we show that there is no constant c <3 such that ρ(n)≤cn. We then exploit the connection between extended special factors and minimal absent words to construct a data structure for computing minimal absent words of a specific length in optimal time for integer alphabets generalising a result by Fujishige et al. [MFCS 2016]. As an application of our data structure, we show how to compare two words over an integer alphabet in optimal time improving on another result by Charalampopoulos et al. [Inf. Comput. 2018].

AB - An extended special factor of a word x is a factor of x whose longest infix can be extended by at least two distinct letters to the left or to the right and still occur in x. It is called extended bispecial if it can be extended in both directions and still occur in x. Let ρ(n) be the maximum number of extended bispecial factors over all words of length n. Almirantis et al. have shown that 2n - 6≤ ρ(n)≤ 3n-4 [WABI 2017]. In this article, we show that there is no constant c <3 such that ρ(n)≤cn. We then exploit the connection between extended special factors and minimal absent words to construct a data structure for computing minimal absent words of a specific length in optimal time for integer alphabets generalising a result by Fujishige et al. [MFCS 2016]. As an application of our data structure, we show how to compare two words over an integer alphabet in optimal time improving on another result by Charalampopoulos et al. [Inf. Comput. 2018].

KW - Minimal absent words

KW - Special factors

KW - String algorithms

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

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

U2 - 10.1007/978-3-030-00479-8_11

DO - 10.1007/978-3-030-00479-8_11

M3 - Conference contribution

AN - SCOPUS:85054880953

SN - 9783030004781

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 131

EP - 138

BT - String Processing and Information Retrieval - 25th International Symposium, SPIRE 2018, Proceedings

A2 - Gagie, Travis

A2 - Moffat, Alistair

A2 - Navarro, Gonzalo

A2 - Cuadros-Vargas, Ernesto

PB - Springer Verlag

T2 - 25th International Symposium on String Processing and Information Retrieval, SPIRE 2018

Y2 - 9 October 2018 through 11 October 2018

ER -

Charalampopoulos P, Crochemore M, Pissis SP. On extended special factors of a word. In Gagie T, Moffat A, Navarro G, Cuadros-Vargas E, editors, String Processing and Information Retrieval - 25th International Symposium, SPIRE 2018, Proceedings. Springer Verlag. 2018. p. 131-138. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-00479-8_11

On extended special factors of a word

Abstract

Publication series

Conference

Funding

Keywords

Access to Document

Persistent URL (handle)

Other files and links

Fingerprint

Cite this