File(s) under embargo

Reason: Publisher requirement.

5

month(s)

12

day(s)

until file(s) become available

Clusters of repetition roots: single chains

conference contribution
posted on 15.02.2021, 11:46 by Szilárd Zsolt Fazekas, Robert Mercas
This work proposes a new approach towards solving an over 20 years old conjecture regarding the maximum number of distinct squares that a word can contain. To this end we look at clusters of repetition roots, that is, the set of positions where the root u of a repetition uℓ occurs. We lay the foundation of this theory by proving basic properties of these clusters and establishing upper bounds on the number of distinct squares when their roots form a chain with respect to the prefix order.

Funding

JSPS KAKENHI Grant Number JP19K11815

History

School

  • Science

Department

  • Computer Science

Published in

SOFSEM 2021: Theory and Practice of Computer Science

Pages

400 - 409

Source

47th International Conference on Current Trends in Theory and Practice of Informatics (SOFSEM 2021)

Publisher

Springer

Version

AM (Accepted Manuscript)

Rights holder

© Springer Nature

Publisher statement

The final authenticated version is available online at https://doi.org/10.1007/978-3-030-67731-2_29.

Acceptance date

22/09/2020

Publication date

2021-01-11

Copyright date

2021

ISBN

9783030677305; 9783030677312

Book series

Lecture Notes in Computer Science; vol. 12607

Language

en

Editor(s)

Tomáš Bureš; Riccardo Dondi; Johann Gamper; Giovanna Guerrini; Tomasz Jurdziński; Claus Pahl; Florian Sikora; Prudence W.H. Wong

Location

Bolzano-Bozen, Italy

Event dates

25th January 2021 - 29th January 2021

Depositor

Dr Robert Mercas. Deposit date: 13 February 2021

Usage metrics

Read the paper on the publisher website

Loughborough Publications

Categories

Exports