[en] In combinatorics on words, a classical topic of study is the number of
specific patterns appearing in infinite sequences. For instance, many works
have been dedicated to studying the so-called factor complexity of infinite
sequences, which gives the number of different factors (contiguous subblocks of
their symbols), as well as abelian complexity, which counts factors up to a
permutation of letters. In this paper, we consider the relatively unexplored
concept of additive complexity, which counts the number of factors up to
additive equivalence. We say that two words are additively equivalent if they
have the same length and the total weight of their letters is equal. Our
contribution is to expand the general knowledge of additive complexity from a
theoretical point of view and consider various famous examples. We show a
particular case of an analog of the long-standing conjecture on the regularity
of the abelian complexity of an automatic sequence. In particular, we use the
formalism of logic, and the software Walnut, to decide related properties of
automatic sequences. We compare the behaviors of additive and abelian
complexities, and we also consider the notion of abelian and additive powers.
Along the way, we present some open questions and conjectures for future work.
Stipulanti, Manon ; Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes
Language :
English
Title :
Additive word complexity and Walnut
Publication date :
2024
Event name :
44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024)
Event organizer :
IIT Gandhinagar
Event place :
Gandhinagar, India
Event date :
December 16-18, 2024
Audience :
International
Journal title :
Leibniz International Proceedings in Informatics
ISSN :
1868-8969
Publisher :
Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, Germany
Volume :
323
Pages :
32:1--32:18
Peer reviewed :
Peer Reviewed verified by ORBi
Funders :
F.R.S.-FNRS - Fonds de la Recherche Scientifique NSERC - Natural Sciences and Engineering Research Council
Funding number :
FNRS 1.C.104.24F; NSERC grants 2018-04118 and 2024-03725
Funding text :
Pierre Popoli is supported by ULiège’s Special Funds for Research, IPD-STEMA
Program. Jeffrey Shallit is supported by NSERC grants 2018-04118 and 2024-03725.
Manon Stipulanti is an FNRS Research Associate supported by the Research grant
1.C.104.24F
Commentary :
21 pages, 6 figures; this is the authors' version (with appendices)
of the same-titled article published in the proceedings of the 44th IARCS
Annual Conference on Foundations of Software Technology and Theoretical
Computer Science (FSTTCS 2024)
scite shows how a scientific paper has been cited by providing the context of the citation, a classification describing whether it supports, mentions, or contrasts the cited claim, and a label indicating in which section the citation was made.
Bibliography
Jean-Paul Allouche, John Campbell, Jeffrey Shallit, and Manon Stipulanti. The reflection complexity of sequences over finite alphabets. arXiv preprint. doi:10.48550/arXiv.2406. 09302.
Jean-Paul Allouche, Michel Dekking, and Martine Queffélec. Hidden automatic sequences. Comb. Theory, 1:15, 2021. Id/No 20. doi:10.5070/C61055386.
Jean-Paul Allouche and Jeffrey Shallit. Automatic sequences: Theory, applications, generalizations. Cambridge University Press, Cambridge, 2003. doi:10.1017/CBO9780511546563.
Jonathan Andrade and Lucas Mol. Avoiding abelian and additive powers in rich words, 2024. arXiv preprint. doi:10.48550/arXiv.2408.15390.
Hayri Ardal, Tom Brown, Veselin Jungić, and Julian Sahasrabudhe. On abelian and additive complexity in infinite words. Integers, 12(5):795–804, 2012. doi:10.1515/ integers-2012-0005.
Graham Banero. On additive complexity of infinite words. J. Integer Seq., 16(1):Article 13.1.5, 20, 2013.
Jean Berstel. Sur les mots sans carré définis par un morphisme. In Automata, languages and programming (Sixth Colloq., Graz, 1979), volume 71 of Lecture Notes in Comput. Sci., pages 16–25. Springer, Berlin-New York, 1979. doi:10.1007/3-540-09510-1_2.
Jean Berstel and Dominique Perrin. The origins of combinatorics on words. Eur. J. Comb., 28(3):996–1022, 2007. doi:10.1016/j.ejc.2005.07.019.
Jean Berstel and Christophe Reutenauer. Noncommutative Rational Series With Applications, volume 137 of Encyclopedia of Mathematics and Its Applications. Cambridge Univ. Press, 2011.
Francine Blanchet-Sadri, James D. Currie, Narad Rampersad, and Nathan Fox. Abelian complexity of fixed point of morphism 0 7→ 012, 1 7→ 02, 2 7→ 1. Integers, 14:A11, 2014. URL: http://math.colgate.edu/%7Eintegers/o11/o11.Abstract.html.
Thomas C. Brown and Allen R. Freedman. Arithmetic progressions in lacunary sets. Rocky Mountain J. Math., 17:587–596, 1987.
Tom Brown. Approximations of additive squares in infinite words. Integers, 12(5):805–809, a22, 2012. doi:10.1515/integers-2012-0006.
Arturo Carpi and Cristiano Maggi. On synchronized sequences and their separators. Theor. Inform. Appl., 35(6):513–524, 2001. doi:10.1051/ita:2001129.
Julien Cassaigne, James D. Currie, Luke Schaeffer, and Jeffrey Shallit. Avoiding three consecutive blocks of the same size and same sum. J. ACM, 61(2):Art. 10, 17, 2014. doi: 10.1145/2590775.
Julien Cassaigne, Sébastien Ferenczi, and Luca Q. Zamboni. Imbalances in Arnoux-Rauzy sequences. Ann. Inst. Fourier, 50(4):1265–1276, 2000. doi:10.5802/aif.1792.
Julien Cassaigne, Gwénaël Richomme, Kalle Saari, and Luca Q. Zamboni. Avoiding abelian powers in binary words with bounded abelian complexity. Int. J. Found. Comput. Sci., 22(4):905–920, 2011. doi:10.1142/S0129054111008489.
Jin Chen, Zhixiong Wen, and Wen Wu. On the additive complexity of a Thue-Morse-like sequence. Discrete Appl. Math., 260:98–108, 2019. doi:10.1016/j.dam.2019.01.008.
Alan Cobham. Uniform tag sequences. Math. Systems Theory, 6:164–192, 1972. doi: 10.1007/BF01706087.
Ethan M. Coven and G. A. Hedlund. Sequences with minimal block growth. Math. Systems Theory, 7:138–153, 1973. doi:10.1007/BF01762232.
James Currie and Narad Rampersad. Recurrent words with constant abelian complexity. Adv. Appl. Math., 47(1):116–124, 2011. doi:10.1016/j.aam.2010.05.001.
Fabien Durand. Cobham’s theorem for substitutions. Journal of the European Mathematical Society, 13(6):1799–1814, September 2011. doi:10.4171/jems/294.
Gabriele Fici, Alessio Langiu, Thierry Lecroq, Arnaud Lefebvre, Filippo Mignosi, Jarkko Peltomäki, and Élise Prieur-Gaston. Abelian powers and repetitions in Sturmian words. Theoret. Comput. Sci., 635:16–34, 2016. doi:10.1016/j.tcs.2016.04.039.
Gabriele Fici, Alessio Langiu, Thierry Lecroq, Arnaud Lefebvre, Filippo Mignosi, and Élise Prieur-Gaston. Abelian repetitions in Sturmian words. In Developments in Language Theory, volume 7907 of Lecture Notes in Comput. Sci., pages 227–238. Springer, Heidelberg, 2013. doi:10.1007/978-3-642-38771-5_21.
Lorenz Halbeisen and Norbert Hungerbühler. An application of Van der Waerden’s theorem in additive number theory. INTEGERS, 0:#A7, 2000. Available online at https://math.colgate.edu/~integers/a7/a7.pdf.
Idrissa Kaboré and Boucaré Kientéga. Abelian complexity of Thue-Morse word over a ternary alphabet. In Combinatorics on words, volume 10432 of Lecture Notes in Comput. Sci., pages 132–143. Springer, Cham, 2017. doi:10.1007/978-3-319-66396-8_13.
M. Lothaire. Combinatorics on words. Cambridge Mathematical Library. Cambridge University Press, Cambridge, 1997. doi:10.1017/CBO9780511566097.
Marston Morse and Gustav A. Hedlund. Symbolic dynamics. II: Sturmian trajectories. Am. J. Math., 62:1–42, 1940. doi:10.2307/2371431.
Aline Parreau, Michel Rigo, Eric Rowland, and Élise Vandomme. A new approach to the 2-regularity of the ℓ-abelian complexity of 2-automatic sequences. Electron. J. Comb., 22(1):research paper p1.27, 44, 2015. URL: www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p27.
Giuseppe Pirillo and Stefano Varricchio. On uniformly repetitive semigroups. Semigroup Forum, 49:125–129, 1994.
Michaël Rao. On some generalizations of abelian power avoidability. Theoret. Comput. Sci., 601:39–46, 2015. doi:10.1016/j.tcs.2015.07.026.
Gwénaël Richomme, Kalle Saari, and Luca Q. Zamboni. Balance and abelian complexity of the Tribonacci word. Adv. in Appl. Math., 45(2):212–231, 2010. doi:10.1016/j.aam.2010.01.006.
Gwénaël Richomme, Kalle Saari, and Luca Q. Zamboni. Abelian complexity of minimal subshifts. J. Lond. Math. Soc. (2), 83(1):79–95, 2011. doi:10.1112/jlms/jdq063.
Michel Rigo and Arnaud Maes. More on generalized automatic sequences. Journal of Automata, Languages, and Combinatorics, 7(3):351–376, 2002. doi:10.25596/jalc-2002-351.
Michel Rigo, Manon Stipulanti, and Markus A. Whiteland. Automaticity and Parikh-collinear morphisms. In Combinatorics on words, volume 13899 of Lecture Notes in Comput. Sci., pages 247–260. Springer, Cham, 2023. doi:10.1007/978-3-031-33180-0_19.
Michel Rigo, Manon Stipulanti, and Markus A. Whiteland. Automatic abelian complexities of Parikh-collinear fixed points, 2024. To be published in Theory Comput. Syst. doi: 10.48550/arXiv.2405.18032.
Julian Sahasrabudhe. Sturmian words and constant additive complexity. Integers, 15:Paper No. A30, 8, 2015.
Jeffrey Shallit. A generalization of automatic sequences. Theoret. Comput. Sci., 61(1):1–16, 1988. doi:10.1016/0304-3975(88)90103-X.
Jeffrey Shallit. The logical approach to automatic sequences—exploring combinatorics on words with Walnut, volume 482 of London Mathematical Society Lecture Note Series. Cambridge University Press, Cambridge, 2023.
Jeffrey Shallit. Note on a Fibonacci parity sequence. Cryptogr. Commun., 15(2):309–315, 2023. doi:10.1007/s12095-022-00592-5.
Neil J. A. Sloane and et al. The On-Line Encyclopedia of Integer Sequences. URL: https://oeis.org.
This website uses cookies to improve user experience. Read more
Save & Close
Accept all
Decline all
Show detailsHide details
Cookie declaration
About cookies
Strictly necessary
Performance
Strictly necessary cookies allow core website functionality such as user login and account management. The website cannot be used properly without strictly necessary cookies.
This cookie is used by Cookie-Script.com service to remember visitor cookie consent preferences. It is necessary for Cookie-Script.com cookie banner to work properly.
Performance cookies are used to see how visitors use the website, eg. analytics cookies. Those cookies cannot be used to directly identify a certain visitor.
Used to store the attribution information, the referrer initially used to visit the website
Cookies are small text files that are placed on your computer by websites that you visit. Websites use cookies to help users navigate efficiently and perform certain functions. Cookies that are required for the website to operate properly are allowed to be set without your permission. All other cookies need to be approved before they can be set in the browser.
You can change your consent to cookie usage at any time on our Privacy Policy page.
