Search

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., Comment: 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)

The correlation measure is a testimony of the pseudorandomness of a sequence $\infw{s}$ and provides information about the independence of some parts of $\infw{s}$ and their shifts. Combined with the well-distribution measure, a sequence possesses good pseudorandomness properties if both measures are relatively small. In combinatorics on words, the famous $b$-automatic sequences are quite far from being pseudorandom, as they have small factor complexity on the one hand and large well-distribution and correlation measures on the other. This paper investigates the pseudorandomness of a specific family of morphic sequences, including classical $b$-automatic sequences. In particular, we show that such sequences have large even-order correlation measures; hence, they are not pseudorandom. We also show that even- and odd-order correlation measures behave differently when considering some simple morphic sequences., Comment: 15 pages, 3 figures

In combinatorics on words, the well-studied factor complexity function $\rho_{\bf x}$ of a sequence ${\bf x}$ over a finite alphabet counts, for any nonnegative integer $n$, the number of distinct length-$n$ factors of $\mathbf{x}$. In this paper, we introduce the reflection complexity function $r_{\bf x}$ to enumerate the factors occurring in a sequence ${\bf x}$, up to reversing the order of symbols in a word. We introduce and prove general results on $r_{\bf x}$ regarding its growth properties and relationship with other complexity functions. We prove a Morse-Hedlund-type result characterizing eventually periodic sequences in terms of their reflection complexity, and we deduce a characterization of Sturmian sequences. Furthermore, we investigate the reflection complexity of quasi-Sturmian, episturmian, $(s+1)$-dimensional billiard, and complementation-symmetric Rote, and rich sequences. Furthermore, we prove that if ${\bf x}$ is $k$-automatic, then $r_{\bf x}$ is computably $k$-regular, and we use the software $\mathtt{Walnut}$ to evaluate the reflection complexity of automatic sequences, such as the Thue-Morse sequence. We note that there are still many unanswered questions about this measure.

Parikh-collinear morphisms have the property that all the Parikh vectors of the images of letters are collinear, i.e., the associated adjacency matrix has rank 1. In the conference DLT-WORDS 2023 we showed that fixed points of Parikh-collinear morphisms are automatic. We also showed that the abelian complexity function of a binary fixed point of such a morphism is automatic under some assumptions. In this note, we fully generalize the latter result. Namely, we show that the abelian complexity function of a fixed point of an arbitrary, possibly erasing, Parikh-collinear morphism is automatic. Furthermore, a deterministic finite automaton with output generating this abelian complexity function is provided by an effective procedure. To that end, we discuss the constant of recognizability of a morphism and the related cutting set., Comment: 18 pages, 2 figures, long version of [M. Rigo, M. Stipulanti, M. A. Whiteland, Automaticity and Parikh-collinear morphisms. In: Combinatorics on Words. Lecture Notes in Comput. Sci., vol. 13899, pp. 247-260. Springer, 2023]

We explore the Ziv-Lempel and Crochemore factorizations of some classical automatic sequences making an extensive use of the theorem prover Walnut., Comment: 15 pages, 2 figures

Generating series are crucial in enumerative combinatorics, analytic combinatorics, and combinatorics on words. Though it might seem at first view that generating Dirichlet series are less used in these fields than ordinary and exponential generating series, there are many notable papers where they play a fundamental role, as can be seen in particular in the work of Flajolet and several of his co-authors. In this paper, we study Dirichlet series of integers with missing digits or blocks of digits in some integer base $b$; i.e., where the summation ranges over the integers whose expansions form some language strictly included in the set of all words over the alphabet $\{0, 1, \dots, b-1\}$ that do not begin with a $0$. We show how to unify and extend results proved by Nathanson in 2021 and by K\"ohler and Spilker in 2009. En route, we encounter several sequences from Sloane's On-Line Encyclopedia of Integer Sequences, as well as some famous $b$-automatic sequences or $b$-regular sequences. We also consider a specific sequence that is not $b$-regular., Comment: 26 pages, 1 figure

We revisit and generalize inequalities for the summatory function of the sum of digits in a given integer base. We prove that several known results can be deduced from a theorem in a 2023 paper by Mohanty, Greenbury, Sarkany, Narayanan, Dingle, Ahnert, and Louis, whose primary scope is the maximum mutational robustness in genotype-phenotype maps., Comment: 10 pages; this is a revised version to appear in Communications in Mathematics

Christol's theorem states that a power series with coefficients in a finite field is algebraic if and only if its coefficient sequence is automatic. A natural question is how the size of a polynomial describing such a sequence relates to the size of an automaton describing the same sequence. Bridy used tools from algebraic geometry to bound the size of the minimal automaton for a sequence, given its minimal polynomial. We produce a new proof of Bridy's bound by embedding algebraic sequences as diagonals of rational functions. Crucially for our interests, our approach can be adapted to work not just over a finite field but over the integers modulo $p^\alpha$., Comment: 29 pages, 2 figures, 2 tables

In formal languages and automata theory, the magic number problem can be formulated as follows: for a given integer n, is it possible to find a number d in the range [n,2^n] such that there is no minimal deterministic finite automaton with d states that can be simulated by an optimal nondeterministic finite automaton with exactly n states? If such a number d exists, it is called magic. In this paper, we consider the magic number problem in the framework of deterministic automata with output, which are known to characterize automatic sequences. More precisely, we investigate magic numbers for periodic sequences viewed as either automatic, regular, or constant-recursive., Comment: 19 pages, 2 figures, 3 tables, accepted at the international conferences WORDS 2023

Firstly studied by Kempa and Prezza in 2018 as the cement of 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 obtain string attractors of prefixes of particular infinite words generalizing k-bonacci words (including the famous Fibonacci word) and related to simple Parry numbers. In fact, our description involves the numeration systems classically derived from the considered morphisms. This extends our previous work published in the international conference WORDS 2023., Comment: Extended version of a paper published in WORDS 2023. The conference version is arXiv:2302.13647v1

Generalizing the notion of the boundary sequence introduced by Chen and Wen, the $n$th term of the $\ell$-boundary sequence of an infinite word is the finite set of pairs $(u,v)$ of prefixes and suffixes of length $\ell$ appearing in factors $uyv$ of length $n+\ell$ ($n\ge \ell\ge 1$). Otherwise stated, for increasing values of $n$, one looks for all pairs of factors of length $\ell$ separated by $n-\ell$ symbols. For the large class of addable abstract numeration systems $S$, we show that if an infinite word is $S$-automatic, then the same holds for its $\ell$-boundary sequence. In particular, they are both morphic (or generated by an HD0L system). To precise the limits of this result, we discuss examples of non-addable numeration systems and $S$-automatic words for which the boundary sequence is nevertheless $S$-automatic and conversely, $S$-automatic words with a boundary sequence that is not $S$-automatic. In the second part of the paper, we study the $\ell$-boundary sequence of a Sturmian word. We show that it is obtained through a sliding block code from the characteristic Sturmian word of the same slope. We also show that it is the image under a morphism of some other characteristic Sturmian word., Comment: 32 pages, 8 figures. Short version: M. Rigo, M. Stipulanti, M. A. Whiteland, On extended boundary sequences of morphic and Sturmian words, MFCS 2022, Leibniz Int. Proc. Inform. 241 (2022), Paper 79

Among all positional numeration systems, the widely studied Bertrand numeration systems are defined by a simple criterion in terms of their numeration languages. In 1989, Bertrand-Mathis characterized them via representations in a real base $\beta$. However, the given condition turns to be not necessary. Hence, the goal of this paper is to provide a correction of Bertrand-Mathis' result. The main difference arises when $\beta$ is a Parry number, in which case are derived two associated Bertrand numeration systems. Along the way, we define a non-canonical $\beta$-shift and study its properties analogously to those of the usual canonical one.

We consider the sequence of integers whose $n$th term has base-$p$ expansion given by the $n$th row of Pascal's triangle modulo $p$ (where $p$ is a prime number). We first present and generalize well-known relations concerning this sequence. Then, with the great help of Sloane's On-Line Encyclopedia of Integer Sequences, we show that it appears naturally as a subsequence of a $2$-regular sequence. Its study provides interesting relations and surprisingly involves odious and evil numbers, Nim-sum and even Gray codes. Furthermore, we examine similar sequences emerging from prime numbers involving alternating sum-of-digits modulo~$p$. This note ends with a discussion about Pascal's pyramid involving trinomial coefficients., Comment: 24 pages, 12 figures

Two words are $k$-binomially equivalent if each subword of length at most $k$ occurs the same number of times in both words. The $k$-binomial complexity of an infinite word is a counting function that maps $n$ to the number of $k$-binomial equivalence classes represented by its factors of length $n$. Cassaigne et al. [Int. J. Found. Comput. S., 22(4) (2011)] characterized a family of morphisms, which we call Parikh-collinear, as those morphisms that map all words to words with bounded $1$-binomial complexity. Firstly, we extend this characterization: they map words with bounded $k$-binomial complexity to words with bounded $(k+1)$-binomial complexity. As a consequence, fixed points of Parikh-collinear morphisms are shown to have bounded $k$-binomial complexity for all $k$. Secondly, we give a new characterization of Sturmian words with respect to their $k$-binomial complexity. Then we characterize recurrent words having, for some $k$, the same $j$-binomial complexity as the Thue-Morse word for all $j\le k$. Finally, inspired by questions raised by Lejeune, we study the relationships between the $k$- and $(k+1)$-binomial complexities of infinite words; as well as the link with the usual factor complexity., Comment: 35 pages, 2 figures. Short version under a different title: M. Rigo, M. Stipulanti, and M. A. Whiteland. Binomial complexities and Parikh-collinear morphisms. In V. Diekert and M. V. Volkov, editors, DLT 2022, volume 13257 of LNCS, 251-262. Springer, 2022. doi:10.1007/978-3-031-05578-2\_20

A word $w$ is said to be closed if it has a proper factor $x$ which occurs exactly twice in $w$, as a prefix and as a suffix of $w$. Based on the concept of Ziv-Lempel factorization, we define the closed $z$-factorization of finite and infinite words. Then we find the closed $z$-factorization of the infinite $m$-bonacci words for all $m \geq 2$. We also classify closed prefixes of the infinite $m$-bonacci words.

Regular sequences generalize the extensively studied automatic sequences. Let $S$ be an abstract numeration system. When the numeration language $L$ is prefix-closed and regular, a sequence is said to be $S$-regular if the module generated by its $S$-kernel is finitely generated. In this paper, we give a new characterization of such sequences in terms of the underlying numeration tree $T(L)$ whose nodes are words of $L$. We may decorate these nodes by the sequence of interest following a breadth-first enumeration. For a prefix-closed regular language $L$, we prove that a sequence is $S$-regular if and only if the tree $T(L)$ decorated by the sequence is linear, i.e., the decoration of a node depends linearly on the decorations of a fixed number of ancestors. Next, we introduce and study regular sequences in a rational base numeration system, whose numeration language is known to be highly non-regular. We motivate and comment our definition that a sequence is $\frac{p}{q}$-regular if the underlying numeration tree decorated by the sequence is linear. We give the first few properties of such sequences, we provide a few examples of them, and we propose a method for guessing $\frac{p}{q}$-regularity. Then we discuss the relationship between $\frac{p}{q}$-automatic sequences and $\frac{p}{q}$-regular sequences. We finally present a graph directed linear representation of a $\frac{p}{q}$-regular sequence. Our study permits us to highlight the places where the regularity of the numeration language plays a predominant role., Comment: 31 pages, 12 figures

The $n$th term of an automatic sequence is the output of a deterministic finite automaton fed with the representation of $n$ in a suitable numeration system. In this paper, instead of considering automatic sequences built on a numeration system with a regular numeration language, we consider those built on languages associated with trees having periodic labeled signatures and, in particular, rational base numeration systems. We obtain two main characterizations of these sequences. The first one is concerned with $r$-block substitutions where $r$ morphisms are applied periodically. In particular, we provide examples of such sequences that are not morphic. The second characterization involves the factors, or subtrees of finite height, of the tree associated with the numeration system and decorated by the terms of the sequence., Comment: 26 pages, 16 figures; final version accepted for publication in Discrete Mathematics & Theoretical Computer Science

The notion of $b$-regular sequences was generalized to abstract numeration systems by Maes and Rigo in 2002. Their definition is based on a notion of $\mathcal{S}$-kernel that extends that of $b$-kernel. However, this definition does not allow us to generalize all of the many characterizations of $b$-regular sequences. In this paper, we present an alternative definition of $\mathcal{S}$-kernel, and hence an alternative definition of $\mathcal{S}$-regular sequences, which enables us to use recognizable formal series in order to generalize most (if not all) known characterizations of $b$-regular sequences to abstract numeration systems. We then give two characterizations of $\mathcal{S}$-automatic sequences as particular $\mathcal{S}$-regular sequences. Next, we present a general method to obtain various families of $\mathcal{S}$-regular sequences by enumerating $\mathcal{S}$-recognizable properties of $\mathcal{S}$-automatic sequences. As an example of the many possible applications of this method, we show that, provided that addition is $\mathcal{S}$-recognizable, the factor complexity of an $\mathcal{S}$-automatic sequence defines an $\mathcal{S}$-regular sequence. In the last part of the paper, we study $\mathcal{S}$-synchronized sequences. Along the way, we prove that the formal series obtained as the composition of a synchronized relation and a recognizable series is recognizable. As a consequence, the composition of an $\mathcal{S}$-synchronized sequence and a $\mathcal{S}$-regular sequence is shown to be $\mathcal{S}$-regular. All our results are presented in an arbitrary dimension $d$ and for an arbitrary semiring $\mathbb{K}$., Comment: 38 pages, 13 figures

We consider numeration systems based on a $d$-tuple $\mathbf{U}=(U_1,\ldots,U_d)$ of sequences of integers and we define $(\mathbf{U},\mathbb{K})$-regular sequences through $\mathbb{K}$-recognizable formal series, where $\mathbb{K}$ is any semiring. We show that, for any $d$-tuple $\mathbf{U}$ of Pisot numeration systems and any commutative semiring $\mathbb{K}$, this definition does not depend on the greediness of the $\mathbf{U}$-representations of integers. The proof is constructive and is based on the fact that the normalization is realizable by a $2d$-tape finite automaton. In particular, we use an ad hoc operation mixing a $2d$-tape automaton and a $\mathbb{K}$-automaton in order to obtain a new $\mathbb{K}$-automaton., Comment: 19 pages, 5 figures ; new revised version

We identify the structure of the lexicographically least word avoiding 5/4-powers on the alphabet of nonnegative integers. Specifically, we show that this word has the form $p \tau(\varphi(z) \varphi^2(z) \cdots)$ where $p, z$ are finite words, $\varphi$ is a 6-uniform morphism, and $\tau$ is a coding. This description yields a recurrence for the $i$th letter, which we use to prove that the sequence of letters is 6-regular with rank 188. More generally, we prove $k$-regularity for a sequence satisfying a recurrence of the same type., Comment: 35 pages, 3 figures

We introduce a variation of the Ziv-Lempel and Crochemore factorizations of words by requiring each factor to be a palindrome. We compute these factorizations for the Fibonacci word, and more generally, for all $m$-bonacci words., Comment: 34 pages

We make certain bounds in Krebs' proof of Cobham's theorem explicit and obtain corresponding upper bounds on the length of a common prefix of an aperiodic $a$-automatic sequence and an aperiodic $b$-automatic sequence, where $a$ and $b$ are multiplicatively independent. We also show that an automatic sequence cannot have arbitrarily large factors in common with a Sturmian sequence., Comment: 17 pages

If $p$ is a prime number, consider a $p$-automatic sequence $(u_n)_{n\ge 0}$, and let $U(X) = \sum_{n\ge 0} u_n X^n \in \mathbb{F}_p[[X]]$ be its generating function. Assume that there exists a formal power series $V(X) = \sum_{n\ge 0} v_n X^n \in \mathbb{F}_p[[X]]$ which is the compositional inverse of $U$, i.e., $U(V(X))=X=V(U(X))$. The problem investigated in this paper is to study the properties of the sequence $(v_n)_{n\ge 0}$. The work was first initiated for the Thue-Morse sequence, and more recently the case of two variations of the Baum-Sweet sequence has been treated. In this paper, we deal with the case of the period-doubling sequence. We first show that the sequence of indices at which the period-doubling sequence takes value $0$ (resp., $1$) is not $k$-regular for any $k\ge 2$. Secondly, we give recurrence relations for its formal inverse, then we easily show that it is $2$-automatic, and we also provide an automaton that generates it. Thirdly, we study the sequence of indices at which this formal inverse takes value $1$, and we show that it is not $k$-regular for any $k\ge 2$ by connecting it to the characteristic sequence of Fibonacci numbers. We leave as an open problem the case of the sequence of indices at which this formal inverse takes value $0$. We end the paper with a remark on the case of generalized Thue-Morse sequences., Comment: 20 pages

The Chen-Fox-Lyndon theorem states that every finite word over a fixed alphabet can be uniquely factorized as a lexicographically nonincreasing sequence of Lyndon words. This theorem can be used to define the family of Lyndon words in a recursive way. If the lexicographic order is reversed in this definition, we obtain a new family of words, which are called the Nyldon words. In this paper, we show that every finite word can be uniquely factorized into a lexicographically nondecreasing sequence of Nyldon words. Otherwise stated, Nyldon words form a complete factorization of the free monoid with respect to the decreasing lexicographic order. Then we investigate this new family of words. In particular, we show that Nyldon words form a right Lazard set., Comment: 28 pages

We pursue the investigation of generalizations of the Pascal triangle based on binomial coefficients of finite words. These coefficients count the number of times a finite word appears as a subsequence of another finite word. The finite words occurring in this paper belong to the language of a Parry numeration system satisfying the Bertrand property, i.e., we can add or remove trailing zeroes to valid representations. It is a folklore fact that the Sierpi\'{n}ski gasket is the limit set, for the Hausdorff distance, of a convergent sequence of normalized compact blocks extracted from the classical Pascal triangle modulo $2$. In a similar way, we describe and study the subset of $[0, 1] \times [0, 1]$ associated with the latter generalization of the Pascal triangle modulo a prime number., Comment: 30 pages; 32 figures

We count the number of distinct (scattered) subwords occurring in the base-b expansion of the non-negative integers. More precisely, we consider the sequence $(S_b(n))_{n\ge 0}$ counting the number of positive entries on each row of a generalization of the Pascal triangle to binomial coefficients of base-$b$ expansions. By using a convenient tree structure, we provide recurrence relations for $(S_b(n))_{n\ge 0}$ leading to the $b$-regularity of the latter sequence. Then we deduce the asymptotics of the summatory function of the sequence $(S_b(n))_{n\ge 0}$., Comment: 22 pages, 9 figures

This paper is about counting the number of distinct (scattered) subwords occurring in a given word. More precisely, we consider the generalization of the Pascal triangle to binomial coefficients of words and the sequence $(S(n))_{n\ge 0}$ counting the number of positive entries on each row. By introducing a convenient tree structure, we provide a recurrence relation for $(S(n))_{n\ge 0}$. This leads to a connection with the $2$-regular Stern-Brocot sequence and the sequence of denominators occurring in the Farey tree. Then we extend our construction to the Zeckendorf numeration system based on the Fibonacci sequence. Again our tree structure permits us to obtain recurrence relations for and the F-regularity of the corresponding sequence., Comment: 28 pages, 10 figures

Many digital functions studied in the literature, e.g., the summatory function of the base-$k$ sum-of-digits function, have a behavior showing some periodic fluctuation. Such functions are usually studied using techniques from analytic number theory or linear algebra. In this paper we develop a method based on exotic numeration systems and we apply it on two examples motivated by the study of generalized Pascal triangles and binomial coefficients of words., Comment: 32 pages, 27 figures

We introduce a generalization of Pascal triangle based on binomial coefficients of finite words. These coefficients count the number of times a word appears as a subsequence of another finite word. Similarly to the Sierpi\'nski gasket that can be built as the limit set, for the Hausdorff distance, of a convergent sequence of normalized compact blocks extracted from Pascal triangle modulo $2$, we describe and study the first properties of the subset of $[0, 1] \times [0, 1]$ associated with this extended Pascal triangle modulo a prime $p$., Comment: 20 pages, 15 figures