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

Mathematical Informatics

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

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.

Original language	English
Title of host publication	String Processing and Information Retrieval - 31st International Symposium, SPIRE 2024, Proceedings
Editors	Zsuzsanna Lipták, Edleno Moura, Karina Figueroa, Ricardo Baeza-Yates
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	174-183
Number of pages	10
ISBN (Print)	9783031721991
DOIs	https://doi.org/10.1007/978-3-031-72200-4_13
Publication status	Published - 2025
Event	31st International Symposium on String Processing and Information Retrieval, SPIRE 2024 - Puerto Vallarta, Mexico Duration: Sept 23 2024 → Sept 25 2024

Publication series

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

Conference

Conference	31st International Symposium on String Processing and Information Retrieval, SPIRE 2024
Country/Territory	Mexico
City	Puerto Vallarta
Period	9/23/24 → 9/25/24

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

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

Cite this

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 et al.
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).

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

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, Mexico, 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 et al. / 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 -