Loughborough University
Browse

Clusters of repetition roots: single chains

Download (398.22 kB)
conference contribution
posted on 2021-02-15, 11:46 authored by Szilárd Zsolt Fazekas, Robert MercasRobert 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

2020-09-22

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

    Loughborough Publications

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC