Inferring strings from full abelian periods

Makoto Nishida; Tomohiro I; Shunsuke Inenaga; Hideo Bannai; Masayuki Takeda

doi:10.1007/978-3-662-48971-0_64

Inferring strings from full abelian periods

Makoto Nishida, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

Mathematical Informatics

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

2 Citations (Scopus)

Abstract

Strings u, v are said to be Abelian equivalent if u is a permutation of the characters appearing in v. A string w is said to have a full Abelian period p if w = w₁ …w_k, where all wi’s are of length p each and are all Abelian equivalent. This paper studies reverse-engineering problems on full Abelian periods. Given a positive integer n and a set D of divisors of n, we show how to compute in O(n) time the lexicographically smallest string of length n which has all elements of D as its full Abelian periods and has the minimum number of full Abelian periods not in D. Moreover, we give an algorithm to enumerate all such strings in amortized constant time per output after O(n)-time preprocessing. Also, we show how to enumerate the strings which have all elements of D as its full Abelian periods in amortized constant time per output after O(n)-time preprocessing.

Original language	English
Title of host publication	Algorithms and Computation - 26th International Symposium, ISAAC 2015, Proceedings
Editors	Khaled Elbassioni, Kazuhisa Makino
Publisher	Springer Verlag
Pages	768-779
Number of pages	12
ISBN (Print)	9783662489703
DOIs	https://doi.org/10.1007/978-3-662-48971-0_64
Publication status	Published - 2015
Event	26th International Symposium on Algorithms and Computation, ISAAC 2015 - Nagoya, Japan Duration: Dec 9 2015 → Dec 11 2015

Publication series

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

Other

Other	26th International Symposium on Algorithms and Computation, ISAAC 2015
Country/Territory	Japan
City	Nagoya
Period	12/9/15 → 12/11/15

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-662-48971-0_64

Cite this

Nishida, M., I, T., Inenaga, S., Bannai, H., & Takeda, M. (2015). Inferring strings from full abelian periods. In K. Elbassioni, & K. Makino (Eds.), Algorithms and Computation - 26th International Symposium, ISAAC 2015, Proceedings (pp. 768-779). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9472). Springer Verlag. https://doi.org/10.1007/978-3-662-48971-0_64

Inferring strings from full abelian periods. / Nishida, Makoto; I, Tomohiro; Inenaga, Shunsuke et al.
Algorithms and Computation - 26th International Symposium, ISAAC 2015, Proceedings. ed. / Khaled Elbassioni; Kazuhisa Makino. Springer Verlag, 2015. p. 768-779 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9472).

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

Nishida, M, I, T, Inenaga, S, Bannai, H & Takeda, M 2015, Inferring strings from full abelian periods. in K Elbassioni & K Makino (eds), Algorithms and Computation - 26th International Symposium, ISAAC 2015, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9472, Springer Verlag, pp. 768-779, 26th International Symposium on Algorithms and Computation, ISAAC 2015, Nagoya, Japan, 12/9/15. https://doi.org/10.1007/978-3-662-48971-0_64

Nishida M, I T, Inenaga S, Bannai H, Takeda M. Inferring strings from full abelian periods. In Elbassioni K, Makino K, editors, Algorithms and Computation - 26th International Symposium, ISAAC 2015, Proceedings. Springer Verlag. 2015. p. 768-779. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-662-48971-0_64

Nishida, Makoto ; I, Tomohiro ; Inenaga, Shunsuke et al. / Inferring strings from full abelian periods. Algorithms and Computation - 26th International Symposium, ISAAC 2015, Proceedings. editor / Khaled Elbassioni ; Kazuhisa Makino. Springer Verlag, 2015. pp. 768-779 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{2917944f1e47473dafac5b50d6d7af65,

title = "Inferring strings from full abelian periods",

abstract = "Strings u, v are said to be Abelian equivalent if u is a permutation of the characters appearing in v. A string w is said to have a full Abelian period p if w = w1 …wk, where all wi{\textquoteright}s are of length p each and are all Abelian equivalent. This paper studies reverse-engineering problems on full Abelian periods. Given a positive integer n and a set D of divisors of n, we show how to compute in O(n) time the lexicographically smallest string of length n which has all elements of D as its full Abelian periods and has the minimum number of full Abelian periods not in D. Moreover, we give an algorithm to enumerate all such strings in amortized constant time per output after O(n)-time preprocessing. Also, we show how to enumerate the strings which have all elements of D as its full Abelian periods in amortized constant time per output after O(n)-time preprocessing.",

author = "Makoto Nishida and Tomohiro I and Shunsuke Inenaga and Hideo Bannai and Masayuki Takeda",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2015. Copyright: Copyright 2019 Elsevier B.V., All rights reserved.; 26th International Symposium on Algorithms and Computation, ISAAC 2015 ; Conference date: 09-12-2015 Through 11-12-2015",

year = "2015",

doi = "10.1007/978-3-662-48971-0_64",

language = "English",

isbn = "9783662489703",

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

publisher = "Springer Verlag",

pages = "768--779",

editor = "Khaled Elbassioni and Kazuhisa Makino",

booktitle = "Algorithms and Computation - 26th International Symposium, ISAAC 2015, Proceedings",

address = "Germany",

}

TY - GEN

T1 - Inferring strings from full abelian periods

AU - Nishida, Makoto

AU - I, Tomohiro

AU - Inenaga, Shunsuke

AU - Bannai, Hideo

AU - Takeda, Masayuki

PY - 2015

Y1 - 2015

N2 - Strings u, v are said to be Abelian equivalent if u is a permutation of the characters appearing in v. A string w is said to have a full Abelian period p if w = w1 …wk, where all wi’s are of length p each and are all Abelian equivalent. This paper studies reverse-engineering problems on full Abelian periods. Given a positive integer n and a set D of divisors of n, we show how to compute in O(n) time the lexicographically smallest string of length n which has all elements of D as its full Abelian periods and has the minimum number of full Abelian periods not in D. Moreover, we give an algorithm to enumerate all such strings in amortized constant time per output after O(n)-time preprocessing. Also, we show how to enumerate the strings which have all elements of D as its full Abelian periods in amortized constant time per output after O(n)-time preprocessing.

AB - Strings u, v are said to be Abelian equivalent if u is a permutation of the characters appearing in v. A string w is said to have a full Abelian period p if w = w1 …wk, where all wi’s are of length p each and are all Abelian equivalent. This paper studies reverse-engineering problems on full Abelian periods. Given a positive integer n and a set D of divisors of n, we show how to compute in O(n) time the lexicographically smallest string of length n which has all elements of D as its full Abelian periods and has the minimum number of full Abelian periods not in D. Moreover, we give an algorithm to enumerate all such strings in amortized constant time per output after O(n)-time preprocessing. Also, we show how to enumerate the strings which have all elements of D as its full Abelian periods in amortized constant time per output after O(n)-time preprocessing.

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

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

U2 - 10.1007/978-3-662-48971-0_64

DO - 10.1007/978-3-662-48971-0_64

M3 - Conference contribution

AN - SCOPUS:84951950947

SN - 9783662489703

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

SP - 768

EP - 779

BT - Algorithms and Computation - 26th International Symposium, ISAAC 2015, Proceedings

A2 - Elbassioni, Khaled

A2 - Makino, Kazuhisa

PB - Springer Verlag

T2 - 26th International Symposium on Algorithms and Computation, ISAAC 2015

Y2 - 9 December 2015 through 11 December 2015

ER -

Inferring strings from full abelian periods

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this