Article (Scientific journals)
String attractors of some simple-Parry automatic sequences
Gheeraert, France; Romana, Giuseppe; Stipulanti, Manon
2024In Theory of Computing Systems
Peer Reviewed verified by ORBi
 

Files


Full Text
sn-article.pdf
Author preprint (574.24 kB) Creative Commons License - Attribution, Non-Commercial, No Derivative
Download

All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
String attractors; Numeration systems; Parry numbers; Automatic sequences; Morphic sequences; Fibonacci word
Abstract :
[en] Firstly studied by Kempa and Prezza in 2018 as the unifying idea behind text compression algorithms, string attractors have become a compelling object of theoretical research within the community of combinatorics on words. In this context, they have been studied for several families of finite and infinite words. In this paper, we focus on string attractors of prefixes of particular automatic infinite words (including the famous period-doubling and k-bonacci words) related to simple-Parry numbers. For a subfamily of these words, we describe string attractors of optimal size, while for the rest of them, we provide nearly optimal-size ones. Such a contribution is of particular interest, since in general finding smallest string attractors is NP-hard. This extends our previous work published in the international conference WORDS 2023.
Disciplines :
Mathematics
Author, co-author :
Gheeraert, France;  UPJV - Université de Picardie Jules Verne [FR] > Mathématique
Romana, Giuseppe;  UniPa - Università degli Studi di Palermo [IT] > Matematica e Informatica
Stipulanti, Manon  ;  Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes
Language :
English
Title :
String attractors of some simple-Parry automatic sequences
Publication date :
2024
Journal title :
Theory of Computing Systems
ISSN :
1432-4350
eISSN :
1433-0490
Publisher :
Springer, Germany
Peer reviewed :
Peer Reviewed verified by ORBi
Funders :
F.R.S.-FNRS - Fonds de la Recherche Scientifique [BE]
Available on ORBi :
since 21 March 2024

Statistics


Number of views
47 (8 by ULiège)
Number of downloads
48 (3 by ULiège)

Scopus citations®
 
0
Scopus citations®
without self-citations
0
OpenCitations
 
0
OpenAlex citations
 
0

Bibliography


Similar publications



Contact ORBi