Combinatorics on Words

A pattern \(\alpha \) (i. e., a string of variables and terminals) matches a word w, if w can be obtained by uniformly replacing the variables of \(\alpha \) by terminal words. The respective matching problem, i. e., deciding whether or not a given pattern matches a given word, is generally -complete, but can be solved in polynomial-time for classes of patterns with restricted structure. In this paper we overview a series of recent results related to efficient matching for patterns with variables, as well as a series of extensions of this problem.

Abelian properties of words is a widely studied field in combinatorics on words. Two finite words are abelian equivalent if for each letter they contain the same numbers of occurrences of this letter. In this paper, we give a short overview of some directions of research on abelian properties of words, and discuss in more detail two new problems: small abelian complexity of two-dimensional words, and abelian subshifts.

Given a (finite or infinite) subset X of the free monoid \(A^*\) over a finite alphabet A, the rank of X is the minimal cardinality of a set F such that \(X \subseteq F^*\). A submonoid M generated by k elements of \(A^*\) is k-maximal if there does not exist another submonoid generated by at most k words containing M. We call a set \(X \subseteq A^*\) primitive if it is the basis of a |X|-maximal submonoid. This extends the notion of primitive word: indeed, \(\{w\}\) is a primitive set if and only if w is a primitive word. By definition, for any set X, there exists a primitive set Y such that \(X \subseteq Y^*\). The set Y is therefore called a primitive root of X. As a main result, we prove that if a set has rank 2, then it has a unique primitive root. This result cannot be extended to sets of rank larger than 2.

For a single word w, we say that the set \(\{x,y\}\) is a binary root of w if w can be written as a concatenation of copies of x and y and \(\{x,y\}\) is a primitive set. We prove that every primitive word w has at most one binary root \(\{x,y\}\) such that \(|x|+|y|<\sqrt{|w|}\). That is, the binary root of a word is unique provided the length of the word is sufficiently large with respect to the size of the root.

Our results are also compared to previous approaches that investigate pseudo-repetitions, where a morphic involutive function \(\theta \) is defined on \(A^*\). In this setting, the notions of \(\theta \)-power, \(\theta \)-primitive and \(\theta \)-root are defined, and it is shown that any word has a unique \(\theta \)-primitive root. This result can be obtained with our approach by showing that a word w is \(\theta \)-primitive if and only if \(\{w, \theta (w)\}\) is a primitive set.

A system of equations is called independent if it is not equivalent to any of its proper subsystems. We consider the following decades-old question: If we fix the number of variables, then what is the maximal size of an independent system of constant-free word equations? This can be easily answered in the trivial cases of one and two variables, but all other cases remain open, even the three-variable case, where the conjectured answer is as small as three. We survey some historical as well as more recent results related to this question, starting with the one known as Ehrenfeucht’s compactness property: Every infinite system is equivalent to a finite subsystem, and consequently an independent system cannot be infinite. We also discuss several variations and related questions on word equations. Finally, we pay special attention to the following result from 2018: The maximal size of an independent system of three-variable equations is at most 18. This is the first such finite upper bound, but hopefully it will not be the last.

Parikh matrices, introduced by Mateescu et al. in 2001, are generalization of the classical Parikh vectors. These special matrices are often utilized in the combinatorial study of words as an elegant tool to compute the number of occurrences of certain subwords in a word. In this paper, we study the determinant of a certain submatrix of a Parikh matrix, where the submatrix preserves the information contained in the original matrix. We present a formula to compute such a determinant, which we term as the Parikh determinant, for any given word. By using a classical result on Parikh matrices, we establish Parikh determinants as a natural combinatorial characteristic of words. Consequently, a new general identity involving the number of occurrences of certain subwords of a word is obtained. Finally, we address some related observations and possible future directions of this study.

In a recent paper of Rampersad et al., the authors conjectured that the smallest possible critical exponent of an infinite balanced word over a 5-letter alphabet is 3/2. We prove this result, using a formulation of first-order logic, the Pell number system, and a machine computation based on finite-state automata.

Rich words are those containing the maximum possible number of distinct palindromes. Several characteristic properties of rich words have been studied; yet the analysis of repetitions in rich words still involves some interesting open problems. We consider lower bounds on the repetition threshold of infinite rich words over 2- and 3-letter alphabets, and construct a candidate infinite rich word over the alphabet \(\varSigma _2=\{0,1\}\) with a small critical exponent of \(2+\sqrt{2}/2\). This represents the first progress on an open problem of Vesti from 2017.

A generalized lexicographic order on words is a lexicographic order where the total order of the alphabet depends on the position of the comparison. A generalized Lyndon word is a finite word which is strictly smallest among its class of rotations with respect to a generalized lexicographic order. This notion can be extended to infinite words: an infinite generalized Lyndon word is an infinite word which is strictly smallest among its class of suffixes. We prove a conjecture of Dolce, Restivo, and Reutenauer: every infinite word has a unique nonincreasing factorization into finite and infinite generalized Lyndon words. When this factorization has finitely many terms, we characterize the last term of the factorization. Our methods also show that the infinite generalized Lyndon words are precisely the words with infinitely many generalized Lyndon prefixes.

The problem of the commutative equivalence of semigroups generated by semi-linear languages is studied. In particular conditions ensuring that the Kleene closure of a bounded semi-linear code is commutatively equivalent to a regular language are investigated.

Using a new approach based on automatic sequences, logic, and a decision procedure, we reprove some old theorems about circularly squarefree words and unbordered conjugates in a new and simpler way. Furthermore, we prove two new results about unbordered conjugates: we complete the classification, due to Harju and Nowotka, of binary words with the maximum number of unbordered conjugates, and we prove that for every possible number, up to the maximum, there exists a word having that number of unbordered conjugates.

For rational \(1<r\le 2\), an undirected r-power is a word of the form \(xyx'\), where x is nonempty, \(x'\in \{x,{x}^{R}\}\), and \(|xyx'|/|xy|=r\). The undirected repetition threshold for k letters, denoted \(\mathrm {URT}(k)\), is the infimum of the set of all r such that undirected r-powers are avoidable on k letters. We first demonstrate that \(\mathrm {URT}(3)=\tfrac{7}{4}\). Then we show that \(\mathrm {URT}(k)\ge \tfrac{k-1}{k-2}\) for all \(k\ge 4\). We conjecture that \(\mathrm {URT}(k)=\tfrac{k-1}{k-2}\) for all \(k\ge 4\), and we confirm this conjecture for \(k\in \{4,8,12\}\).

Following earlier work by Aldo de Luca and others, we study trapezoidal words and their prefixes, with respect to their characteristic parameters K and R (length of shortest unrepeated suffix, and shortest length without right special factors, respectively), as well as their symmetric versions H and L. We consider the distinction between closed (i.e., periodic-like) and open prefixes, and between Sturmian and non-Sturmian ones. Our main results characterize right special and strictly bispecial trapezoidal words, as done by de Luca and Mignosi for Sturmian words.

A shift space (or its set of factors) is eventually dendric if the possible extensions of all long enough factors are described by a graph which is a tree. We prove two results on eventually dendric shifts. First, all sets of return words to long enough words have the same cardinality. Next, this class of shifts is closed under complete bifix decoding.

Given a finite word w over a finite alphabet V, we may construct a graph with vertex set V and an edge between to elements of V if and only if they alternate in the word w. This is the notion of word-representability of graphs. In this paper, we first study minimal length words which represent graphs, giving an explicit formula for both the length and the number of such words in the case of trees and cycles. Then we extend this notion to study the graphs representable with other patterns in words, proving in all cases aside from one (still unknown to us), all graphs are representable by all other patterns. Finally, we pose a few open problems for further work.

We consider q-coloured words, that is words on \(\left\{ {{1},\dots ,{q}}\right\} \) where no two consecutive letters are equal. Motivated by multipartite colouring games with nonsignalling resources, we are interested in random q-coloured words satisfying a k-localisability property. More precisely, the probability of containing any given pair of words as subwords spaced at least k letters apart can depend only on their lengths. We focus on the issue of the smallest alphabet size q for which a probability distribution for such random words can exist. For \(k = 1\), we prove a lower bound of \(q \geqslant 4\). The bound is optimal because there exists a suitable distribution for random 4-colourings that was constructed by Holroyd and Liggett in 2015. Our lower bound can be generalized to k-localisable random words where the letters of each subword of \(k+1\) letters must be pairwise different. We show that the alphabet size in this case must be at least \((k+1) \cdot (1+1/k)^k\).

Prefix codes such as Huffman codes are commonly used for loseless data compression. The class of synchronizing codes is often chosen to improve error resilience or to enable parallel decoding of data. Such codes have a special sequence whose occurrence realigns decoding process leading to recovery from errors in a data stream. In the present paper we identify a class of codes whose synchronizability depends only on the lengths of codewords. Namely, we show that every maximal finite prefix code with only two codeword lengths is synchronizing if and only if these lengths are coprime.

We reformulate the classical result by Juhani Karhumäki characterizing intersections of two languages of the form \(\{x,y\}^*\cap \{u,v\}^*\). We use the terminology of morphisms which allows to formulate the result in a shorter and more transparent way.

We study infinite words fixed by a morphism and their derived words. A derived word is a coding of return words to a factor. We exhibit two examples of sets of morphisms which are closed under derivation—any derived word with respect to any factor of the fixed point is again fixed by a morphism from this set. The first example involves standard episturmian morphisms, and the second concerns the period doubling morphism.

Consider k-binomial equivalence: two finite words are equivalent if they share the same subwords of length at most k with the same multiplicities. With this relation, the k-binomial complexity of an infinite word \(\mathbf {x}\) maps the integer n to the number of pairwise non-equivalent factors of length n occurring in \(\mathbf {x}\). In this paper based on the notion of template introduced by Currie et al., we show that, for all \(k\ge 2\), the k-binomial complexity of the Tribonacci word coincides with its usual factor complexity \(p(n)=2n+1\). A similar result was already known for Sturmian words, but the proof relies on completely different techniques that seemingly could not be applied for Tribonacci.

For an Arnoux–Rauzy sequence \(\mathbf {\mathbf u}\) we describe the set \(\text {Der}(\mathbf {\mathbf u})\) of derived sequences corresponding to all nonempty prefixes of \(\mathbf {\mathbf u}\) using the normalized directive sequence of \(\mathbf {\mathbf u}\). As a corollary, we show that all derived sequences of \(\mathbf {\mathbf u}\) are also Arnoux–Rauzy sequences. Moreover, if \(\mathbf {\mathbf u}\) is primitive substitutive, we precisely determine the cardinality of the set \(\text {Der}(\mathbf {\mathbf u})\).

We start by considering binary words containing the minimum possible numbers of squares and antisquares (where an antisquare is a word of the form \(x \overline{x}\)), and we completely classify which possibilities can occur. We consider avoiding xp(x), where p is any permutation of the underlying alphabet, and xt(x), where t is any transformation of the underlying alphabet. Finally, we prove the existence of an infinite binary word simultaneously avoiding all occurrences of xh(x) for every nonerasing morphism h and all sufficiently large words x.

The abelian critical exponent of an infinite word w is defined as the maximum ratio between the exponent and the period of an abelian power occurring in w. It was shown by Fici et al. that the set of finite abelian critical exponents of Sturmian words coincides with the Lagrange spectrum. This spectrum contains every large enough positive real number. We construct words whose abelian critical exponents fill the remaining gaps, that is, we prove that for each nonnegative real number \(\theta \) there exists an infinite word having abelian critical exponent \(\theta \). We also extend this result to the k-abelian setting.

A finite word w with \(\vert w\vert =n\) contains at most \(n+1\) distinct palindromic factors. If the bound \(n+1\) is attained, the word w is called rich. Let \({{\,\mathrm{F}\,}}(w)\) be the set of factors of the word w. It is known that there are pairs of rich words that cannot be factors of a same rich word. However it is an open question how to decide for a given pair of rich words u, v if there is a rich word w such that \(\{u,v\}\subseteq {{\,\mathrm{F}\,}}(w)\). We present a response to this open question:

If \(w_1, w_2,w\) are rich words, \(m=\max {\{\vert w_1\vert ,\vert w_2\vert \}}\), and \(\{w_1,w_2\}\subseteq {{\,\mathrm{F}\,}}(w)\) then there exists also a rich word \(\bar{w}\) such that \(\{w_1,w_2\}\subseteq {{\,\mathrm{F}\,}}(\bar{w})\) and \(\vert \bar{w}\vert \le m2^{k(m)+2}\), where \(k(m)=(q+1)m^2(4q^{10}m)^{\log _2{m}}\) and q is the size of the alphabet. Hence it is enough to check all rich words of length equal or lower to \(m2^{k(m)+2}\) in order to decide if there is a rich word containing factors \(w_1,w_2\).

We study mortal words and words of minimum non-zero rank (in particular, synchronizing words) in strongly connected unambiguous automata. We show that every n-state strongly connected unambiguous automaton admits a word of minimum non-zero rank of length at most \(n^5\), and this word can be found in polynomial time. We show that for words of minimum rank this upper bound can be lowered to \(O(n^3 (\log n)^4)\) for prefix automata of finite codes and to \(O(n^3 \log n)\) for prefix automata of complete finite codes. We also provide quadratic lower bounds on the length of shortest mortal words for several classes of deterministic automata.

The set of discrete lattice paths from (0, 0) to (n, n) with North and East steps (i.e. words \(w \in \{\,x,y\,\}^{*}\) such that \(|w|_{x} = |w|_{y} = n\)) has a canonical monoid structure inherited from the bijection with the set of join-continuous map s from the chain \(\{\,0,1,\ldots ,n\,\}\) to itself. We explicitly describe this monoid structure and, relying on a general characterization of idempotent join-continuous map s from a complete lattice to itself, we characterize idempotent paths as upper zigzag paths. We argue that these paths are counted by the odd Fibonacci numbers. Our method yields a geometric/combinatorial proof of counting results, due to Howie and to Laradji and Umar, for idempotents in monoids of monotone endomap s on finite chains.