Detecting regularities on grammar-compressed strings

Tomohiro I; Wataru Matsubara; Kouji Shimohira; Shunsuke Inenaga; Hideo Bannai; Masayuki Takeda; Kazuyuki Narisawa; Ayumi Shinohara

doi:10.1007/978-3-642-40313-2_51

Detecting regularities on grammar-compressed strings

Tomohiro I, Wataru Matsubara, Kouji Shimohira, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Kazuyuki Narisawa, Ayumi Shinohara

INF - System Information Sciences

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

2 Citations (Scopus)

Abstract

We solve the problems of detecting and counting various forms of regularities in a string represented as a Straight Line Program (SLP). Given an SLP of size n that represents a string s of length N, our algorithm computes all runs and squares in s in O(n³ h) time and O(n²) space, where h is the height of the derivation tree of the SLP. We also show an algorithm to compute all gapped-palindromes in O(n³ h + gnhlog N) time and O(n²) space, where g is the length of the gap. The key technique of the above solution also allows us to compute the periods and covers of the string in O(n² h) time and O(nh(n + log² N)) time, respectively.

Original language	English
Title of host publication	Mathematical Foundations of Computer Science 2013 - 38th International Symposium, MFCS 2013, Proceedings
Publisher	Springer Verlag
Pages	571-582
Number of pages	12
ISBN (Print)	9783642403125
DOIs	https://doi.org/10.1007/978-3-642-40313-2_51
Publication status	Published - 2013
Event	38th International Symposium on Mathematical Foundations of Computer Science, MFCS 2013 - Klosterneuburg, Austria Duration: 2013 Aug 26 → 2013 Aug 30

Publication series

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

Conference

Conference	38th International Symposium on Mathematical Foundations of Computer Science, MFCS 2013
Country/Territory	Austria
City	Klosterneuburg
Period	13/8/26 → 13/8/30

Access to Document

10.1007/978-3-642-40313-2_51

Cite this

I, T., Matsubara, W., Shimohira, K., Inenaga, S., Bannai, H., Takeda, M., Narisawa, K., & Shinohara, A. (2013). Detecting regularities on grammar-compressed strings. In Mathematical Foundations of Computer Science 2013 - 38th International Symposium, MFCS 2013, Proceedings (pp. 571-582). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8087). Springer Verlag. https://doi.org/10.1007/978-3-642-40313-2_51

I, Tomohiro ; Matsubara, Wataru ; Shimohira, Kouji et al. / Detecting regularities on grammar-compressed strings. Mathematical Foundations of Computer Science 2013 - 38th International Symposium, MFCS 2013, Proceedings. Springer Verlag, 2013. pp. 571-582 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{9fa4e8b940174d64926f21e09cdec2e2,

title = "Detecting regularities on grammar-compressed strings",

abstract = "We solve the problems of detecting and counting various forms of regularities in a string represented as a Straight Line Program (SLP). Given an SLP of size n that represents a string s of length N, our algorithm computes all runs and squares in s in O(n3 h) time and O(n2) space, where h is the height of the derivation tree of the SLP. We also show an algorithm to compute all gapped-palindromes in O(n3 h + gnhlog N) time and O(n2) space, where g is the length of the gap. The key technique of the above solution also allows us to compute the periods and covers of the string in O(n2 h) time and O(nh(n + log2 N)) time, respectively.",

author = "Tomohiro I and Wataru Matsubara and Kouji Shimohira and Shunsuke Inenaga and Hideo Bannai and Masayuki Takeda and Kazuyuki Narisawa and Ayumi Shinohara",

year = "2013",

doi = "10.1007/978-3-642-40313-2_51",

language = "English",

isbn = "9783642403125",

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

publisher = "Springer Verlag",

pages = "571--582",

booktitle = "Mathematical Foundations of Computer Science 2013 - 38th International Symposium, MFCS 2013, Proceedings",

address = "Germany",

note = "38th International Symposium on Mathematical Foundations of Computer Science, MFCS 2013 ; Conference date: 26-08-2013 Through 30-08-2013",

}

I, T, Matsubara, W, Shimohira, K, Inenaga, S, Bannai, H, Takeda, M, Narisawa, K & Shinohara, A 2013, Detecting regularities on grammar-compressed strings. in Mathematical Foundations of Computer Science 2013 - 38th International Symposium, MFCS 2013, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8087, Springer Verlag, pp. 571-582, 38th International Symposium on Mathematical Foundations of Computer Science, MFCS 2013, Klosterneuburg, Austria, 13/8/26. https://doi.org/10.1007/978-3-642-40313-2_51

Detecting regularities on grammar-compressed strings. / I, Tomohiro; Matsubara, Wataru; Shimohira, Kouji et al.
Mathematical Foundations of Computer Science 2013 - 38th International Symposium, MFCS 2013, Proceedings. Springer Verlag, 2013. p. 571-582 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8087).

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

TY - GEN

T1 - Detecting regularities on grammar-compressed strings

AU - I, Tomohiro

AU - Matsubara, Wataru

AU - Shimohira, Kouji

AU - Inenaga, Shunsuke

AU - Bannai, Hideo

AU - Takeda, Masayuki

AU - Narisawa, Kazuyuki

AU - Shinohara, Ayumi

PY - 2013

Y1 - 2013

N2 - We solve the problems of detecting and counting various forms of regularities in a string represented as a Straight Line Program (SLP). Given an SLP of size n that represents a string s of length N, our algorithm computes all runs and squares in s in O(n3 h) time and O(n2) space, where h is the height of the derivation tree of the SLP. We also show an algorithm to compute all gapped-palindromes in O(n3 h + gnhlog N) time and O(n2) space, where g is the length of the gap. The key technique of the above solution also allows us to compute the periods and covers of the string in O(n2 h) time and O(nh(n + log2 N)) time, respectively.

AB - We solve the problems of detecting and counting various forms of regularities in a string represented as a Straight Line Program (SLP). Given an SLP of size n that represents a string s of length N, our algorithm computes all runs and squares in s in O(n3 h) time and O(n2) space, where h is the height of the derivation tree of the SLP. We also show an algorithm to compute all gapped-palindromes in O(n3 h + gnhlog N) time and O(n2) space, where g is the length of the gap. The key technique of the above solution also allows us to compute the periods and covers of the string in O(n2 h) time and O(nh(n + log2 N)) time, respectively.

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

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

U2 - 10.1007/978-3-642-40313-2_51

DO - 10.1007/978-3-642-40313-2_51

M3 - Conference contribution

AN - SCOPUS:84885196704

SN - 9783642403125

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

SP - 571

EP - 582

BT - Mathematical Foundations of Computer Science 2013 - 38th International Symposium, MFCS 2013, Proceedings

PB - Springer Verlag

T2 - 38th International Symposium on Mathematical Foundations of Computer Science, MFCS 2013

Y2 - 26 August 2013 through 30 August 2013

ER -

I T, Matsubara W, Shimohira K, Inenaga S, Bannai H, Takeda M et al. Detecting regularities on grammar-compressed strings. In Mathematical Foundations of Computer Science 2013 - 38th International Symposium, MFCS 2013, Proceedings. Springer Verlag. 2013. p. 571-582. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-40313-2_51

Detecting regularities on grammar-compressed strings

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this