Computing Covers Under Substring Consistent Equivalence Relations

Natsumi Kikuchi; Diptarama Hendrian; Ryo Yoshinaka; Ayumi Shinohara

doi:10.1007/978-3-030-59212-7_10

Computing Covers Under Substring Consistent Equivalence Relations

Natsumi Kikuchi, Diptarama Hendrian, Ryo Yoshinaka, Ayumi Shinohara

INF - System Information Sciences

Tohoku University

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

3 Citations (Scopus)

Abstract

Covers are a kind of quasiperiodicity in strings. A string C is a cover of another string T if any position of T is inside some occurrence of C in T. The shortest and longest cover arrays of T have the lengths of the shortest and longest covers of each prefix of T, respectively. The literature has proposed linear-time algorithms computing longest and shortest cover arrays taking border arrays as input. An equivalence relation over strings is called a substring consistent equivalence relation (SCER) iff implies (1) and (2) for all. In this paper, we generalize the notion of covers for SCERs and prove that existing algorithms to compute the shortest cover array and the longest cover array of a string T under the identity relation will work for any SCERs taking the accordingly generalized border arrays.

Original language	English
Title of host publication	String Processing and Information Retrieval - 27th International Symposium, SPIRE 2020, Proceedings
Editors	Christina Boucher, Sharma V. Thankachan
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	131-146
Number of pages	16
ISBN (Print)	9783030592110
DOIs	https://doi.org/10.1007/978-3-030-59212-7_10
Publication status	Published - 2020
Event	27th International Symposium on String Processing and Information Retrieval, SPIRE 2020 - Orlando, United States Duration: 2020 Oct 13 → 2020 Oct 15

Publication series

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

Conference

Conference	27th International Symposium on String Processing and Information Retrieval, SPIRE 2020
Country/Territory	United States
City	Orlando
Period	20/10/13 → 20/10/15

Keywords

String covers
String regularities
Substring consistent equivalence relations

Access to Document

10.1007/978-3-030-59212-7_10

Cite this

Kikuchi, N., Hendrian, D., Yoshinaka, R., & Shinohara, A. (2020). Computing Covers Under Substring Consistent Equivalence Relations. In C. Boucher, & S. V. Thankachan (Eds.), String Processing and Information Retrieval - 27th International Symposium, SPIRE 2020, Proceedings (pp. 131-146). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12303 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-030-59212-7_10

Kikuchi, Natsumi ; Hendrian, Diptarama ; Yoshinaka, Ryo et al. / Computing Covers Under Substring Consistent Equivalence Relations. String Processing and Information Retrieval - 27th International Symposium, SPIRE 2020, Proceedings. editor / Christina Boucher ; Sharma V. Thankachan. Springer Science and Business Media Deutschland GmbH, 2020. pp. 131-146 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{1685f012141540d1a4de62b9e5b39c86,

title = "Computing Covers Under Substring Consistent Equivalence Relations",

abstract = "Covers are a kind of quasiperiodicity in strings. A string C is a cover of another string T if any position of T is inside some occurrence of C in T. The shortest and longest cover arrays of T have the lengths of the shortest and longest covers of each prefix of T, respectively. The literature has proposed linear-time algorithms computing longest and shortest cover arrays taking border arrays as input. An equivalence relation over strings is called a substring consistent equivalence relation (SCER) iff implies (1) and (2) for all. In this paper, we generalize the notion of covers for SCERs and prove that existing algorithms to compute the shortest cover array and the longest cover array of a string T under the identity relation will work for any SCERs taking the accordingly generalized border arrays.",

keywords = "String covers, String regularities, Substring consistent equivalence relations",

author = "Natsumi Kikuchi and Diptarama Hendrian and Ryo Yoshinaka and Ayumi Shinohara",

note = "Publisher Copyright: {\textcopyright} 2020, Springer Nature Switzerland AG.; 27th International Symposium on String Processing and Information Retrieval, SPIRE 2020 ; Conference date: 13-10-2020 Through 15-10-2020",

year = "2020",

doi = "10.1007/978-3-030-59212-7_10",

language = "English",

isbn = "9783030592110",

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

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "131--146",

editor = "Christina Boucher and Thankachan, {Sharma V.}",

booktitle = "String Processing and Information Retrieval - 27th International Symposium, SPIRE 2020, Proceedings",

address = "Germany",

}

Kikuchi, N, Hendrian, D , Yoshinaka, R & Shinohara, A 2020, Computing Covers Under Substring Consistent Equivalence Relations. in C Boucher & SV Thankachan (eds), String Processing and Information Retrieval - 27th International Symposium, SPIRE 2020, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12303 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 131-146, 27th International Symposium on String Processing and Information Retrieval, SPIRE 2020, Orlando, United States, 20/10/13. https://doi.org/10.1007/978-3-030-59212-7_10

Computing Covers Under Substring Consistent Equivalence Relations. / Kikuchi, Natsumi; Hendrian, Diptarama ; Yoshinaka, Ryo et al.
String Processing and Information Retrieval - 27th International Symposium, SPIRE 2020, Proceedings. ed. / Christina Boucher; Sharma V. Thankachan. Springer Science and Business Media Deutschland GmbH, 2020. p. 131-146 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12303 LNCS).

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

TY - GEN

T1 - Computing Covers Under Substring Consistent Equivalence Relations

AU - Kikuchi, Natsumi

AU - Hendrian, Diptarama

AU - Yoshinaka, Ryo

AU - Shinohara, Ayumi

PY - 2020

Y1 - 2020

N2 - Covers are a kind of quasiperiodicity in strings. A string C is a cover of another string T if any position of T is inside some occurrence of C in T. The shortest and longest cover arrays of T have the lengths of the shortest and longest covers of each prefix of T, respectively. The literature has proposed linear-time algorithms computing longest and shortest cover arrays taking border arrays as input. An equivalence relation over strings is called a substring consistent equivalence relation (SCER) iff implies (1) and (2) for all. In this paper, we generalize the notion of covers for SCERs and prove that existing algorithms to compute the shortest cover array and the longest cover array of a string T under the identity relation will work for any SCERs taking the accordingly generalized border arrays.

AB - Covers are a kind of quasiperiodicity in strings. A string C is a cover of another string T if any position of T is inside some occurrence of C in T. The shortest and longest cover arrays of T have the lengths of the shortest and longest covers of each prefix of T, respectively. The literature has proposed linear-time algorithms computing longest and shortest cover arrays taking border arrays as input. An equivalence relation over strings is called a substring consistent equivalence relation (SCER) iff implies (1) and (2) for all. In this paper, we generalize the notion of covers for SCERs and prove that existing algorithms to compute the shortest cover array and the longest cover array of a string T under the identity relation will work for any SCERs taking the accordingly generalized border arrays.

KW - String covers

KW - String regularities

KW - Substring consistent equivalence relations

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

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

U2 - 10.1007/978-3-030-59212-7_10

DO - 10.1007/978-3-030-59212-7_10

M3 - Conference contribution

AN - SCOPUS:85092079149

SN - 9783030592110

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

SP - 131

EP - 146

BT - String Processing and Information Retrieval - 27th International Symposium, SPIRE 2020, Proceedings

A2 - Boucher, Christina

A2 - Thankachan, Sharma V.

PB - Springer Science and Business Media Deutschland GmbH

T2 - 27th International Symposium on String Processing and Information Retrieval, SPIRE 2020

Y2 - 13 October 2020 through 15 October 2020

ER -

Kikuchi N, Hendrian D , Yoshinaka R , Shinohara A. Computing Covers Under Substring Consistent Equivalence Relations. In Boucher C, Thankachan SV, editors, String Processing and Information Retrieval - 27th International Symposium, SPIRE 2020, Proceedings. Springer Science and Business Media Deutschland GmbH. 2020. p. 131-146. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-59212-7_10

Computing Covers Under Substring Consistent Equivalence Relations

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this