On the Number of Non-equivalent Parameterized Squares in a String

Rikuya Hamai; Kazushi Taketsugu; Yuto Nakashima; Shunsuke Inenaga; Hideo Bannai

doi:10.1007/978-3-031-72200-4_13

On the Number of Non-equivalent Parameterized Squares in a String

Rikuya Hamai, Kazushi Taketsugu, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai

数理情報

研究成果: 書籍/レポートタイプへの寄稿 › 会議への寄与

抄録

A string s is called a parameterized square when s=xy for strings x, y and x and y are parameterized equivalent. Kociumaka et al. showed the number of parameterized squares, which are non-equivalent in parameterized equivalence, in a string of length n that contains σ distinct characters is at most 2σ!n [TCS 2016]. In this paper, we show that the maximum number of non-equivalent parameterized squares is less than σn, which significantly improves the best-known upper bound by Kociumaka et al.

本文言語	英語
ホスト出版物のタイトル	String Processing and Information Retrieval - 31st International Symposium, SPIRE 2024, Proceedings
編集者	Zsuzsanna Lipták, Edleno Moura, Karina Figueroa, Ricardo Baeza-Yates
出版社	Springer Science and Business Media Deutschland GmbH
ページ	174-183
ページ数	10
ISBN（印刷版）	9783031721991
DOI	https://doi.org/10.1007/978-3-031-72200-4_13
出版ステータス	出版済み - 2025
イベント	31st International Symposium on String Processing and Information Retrieval, SPIRE 2024 - Puerto Vallarta, メキシコ継続期間: 9月 23 2024 → 9月 25 2024

出版物シリーズ

名前	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
巻	14899 LNCS
ISSN（印刷版）	0302-9743
ISSN（電子版）	1611-3349

会議

会議	31st International Symposium on String Processing and Information Retrieval, SPIRE 2024
国/地域	メキシコ
City	Puerto Vallarta
Period	9/23/24 → 9/25/24

!!!All Science Journal Classification (ASJC) codes

理論的コンピュータサイエンス
コンピュータサイエンス一般

文献へのアクセス

10.1007/978-3-031-72200-4_13

他のファイルとリンク

引用スタイル

Hamai, R., Taketsugu, K., Nakashima, Y., Inenaga, S., & Bannai, H. (2025). On the Number of Non-equivalent Parameterized Squares in a String. In Z. Lipták, E. Moura, K. Figueroa, & R. Baeza-Yates (Eds.), String Processing and Information Retrieval - 31st International Symposium, SPIRE 2024, Proceedings (pp. 174-183). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14899 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-031-72200-4_13

On the Number of Non-equivalent Parameterized Squares in a String. / Hamai, Rikuya; Taketsugu, Kazushi; Nakashima, Yuto その他.
String Processing and Information Retrieval - 31st International Symposium, SPIRE 2024, Proceedings. ed. / Zsuzsanna Lipták; Edleno Moura; Karina Figueroa; Ricardo Baeza-Yates. Springer Science and Business Media Deutschland GmbH, 2025. p. 174-183 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14899 LNCS).

研究成果: 書籍/レポートタイプへの寄稿 › 会議への寄与

Hamai, R, Taketsugu, K, Nakashima, Y , Inenaga, S & Bannai, H 2025, On the Number of Non-equivalent Parameterized Squares in a String. in Z Lipták, E Moura, K Figueroa & R Baeza-Yates (eds), String Processing and Information Retrieval - 31st International Symposium, SPIRE 2024, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 14899 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 174-183, 31st International Symposium on String Processing and Information Retrieval, SPIRE 2024, Puerto Vallarta, メキシコ, 9/23/24. https://doi.org/10.1007/978-3-031-72200-4_13

Hamai R, Taketsugu K, Nakashima Y , Inenaga S, Bannai H. On the Number of Non-equivalent Parameterized Squares in a String. In Lipták Z, Moura E, Figueroa K, Baeza-Yates R, editors, String Processing and Information Retrieval - 31st International Symposium, SPIRE 2024, Proceedings. Springer Science and Business Media Deutschland GmbH. 2025. p. 174-183. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-72200-4_13

Hamai, Rikuya ; Taketsugu, Kazushi ; Nakashima, Yuto その他. / On the Number of Non-equivalent Parameterized Squares in a String. String Processing and Information Retrieval - 31st International Symposium, SPIRE 2024, Proceedings. editor / Zsuzsanna Lipták ; Edleno Moura ; Karina Figueroa ; Ricardo Baeza-Yates. Springer Science and Business Media Deutschland GmbH, 2025. pp. 174-183 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{a9327845e0124789b91b941134977329,

title = "On the Number of Non-equivalent Parameterized Squares in a String",

abstract = "A string s is called a parameterized square when s=xy for strings x, y and x and y are parameterized equivalent. Kociumaka et al. showed the number of parameterized squares, which are non-equivalent in parameterized equivalence, in a string of length n that contains σ distinct characters is at most 2σ!n [TCS 2016]. In this paper, we show that the maximum number of non-equivalent parameterized squares is less than σn, which significantly improves the best-known upper bound by Kociumaka et al.",

keywords = "Parameterized equivalence of strings, Periodicity, Squares",

author = "Rikuya Hamai and Kazushi Taketsugu and Yuto Nakashima and Shunsuke Inenaga and Hideo Bannai",

note = "Publisher Copyright: {\textcopyright} The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.; 31st International Symposium on String Processing and Information Retrieval, SPIRE 2024 ; Conference date: 23-09-2024 Through 25-09-2024",

year = "2025",

doi = "10.1007/978-3-031-72200-4_13",

language = "English",

isbn = "9783031721991",

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 = "174--183",

editor = "Zsuzsanna Lipt{\'a}k and Edleno Moura and Karina Figueroa and Ricardo Baeza-Yates",

booktitle = "String Processing and Information Retrieval - 31st International Symposium, SPIRE 2024, Proceedings",

address = "Germany",

}

TY - GEN

T1 - On the Number of Non-equivalent Parameterized Squares in a String

AU - Hamai, Rikuya

AU - Taketsugu, Kazushi

AU - Nakashima, Yuto

AU - Inenaga, Shunsuke

AU - Bannai, Hideo

N1 - Publisher Copyright: © The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.

PY - 2025

Y1 - 2025

N2 - A string s is called a parameterized square when s=xy for strings x, y and x and y are parameterized equivalent. Kociumaka et al. showed the number of parameterized squares, which are non-equivalent in parameterized equivalence, in a string of length n that contains σ distinct characters is at most 2σ!n [TCS 2016]. In this paper, we show that the maximum number of non-equivalent parameterized squares is less than σn, which significantly improves the best-known upper bound by Kociumaka et al.

AB - A string s is called a parameterized square when s=xy for strings x, y and x and y are parameterized equivalent. Kociumaka et al. showed the number of parameterized squares, which are non-equivalent in parameterized equivalence, in a string of length n that contains σ distinct characters is at most 2σ!n [TCS 2016]. In this paper, we show that the maximum number of non-equivalent parameterized squares is less than σn, which significantly improves the best-known upper bound by Kociumaka et al.

KW - Parameterized equivalence of strings

KW - Periodicity

KW - Squares

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

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

U2 - 10.1007/978-3-031-72200-4_13

DO - 10.1007/978-3-031-72200-4_13

M3 - Conference contribution

AN - SCOPUS:85205374861

SN - 9783031721991

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

SP - 174

EP - 183

BT - String Processing and Information Retrieval - 31st International Symposium, SPIRE 2024, Proceedings

A2 - Lipták, Zsuzsanna

A2 - Moura, Edleno

A2 - Figueroa, Karina

A2 - Baeza-Yates, Ricardo

PB - Springer Science and Business Media Deutschland GmbH

T2 - 31st International Symposium on String Processing and Information Retrieval, SPIRE 2024

Y2 - 23 September 2024 through 25 September 2024

ER -