Search

We revisit a classic theorem of Frougny and Sakarovitch concerning automata for $φ$-representations, and show how to obtain it in a different and more computationally direct way. Using it, we can find simple, induction-free proofs of existing results in the literature about these representations, in a uniform and straightforward manner. In particular, we can easily and "automatically'' recover many of the results of recent papers of Dekking and Van Loon. We also obtain a number of new results on $φ$-representations.

We show how to obtain, via a unified framework provided by logic and automata theory, many classical results of Brillhart and Morton on Rudin-Shapiro sums. The techniques also facilitate easy proofs for new results., Comment: This is the full version of a paper that has been accepted to the WORDS 2023 conference in Umea, Sweden

We prove a 2018 conjecture of Krawchuk and Rampersad on the extremal behavior of $c(n)$, where $c(n)$ counts the number of length-$n$ factors of the Thue-Morse word $\mathbf{t}$, up to cyclic rotation.

We study various aspects of Dyck words appearing in binary sequences, where $0$ is treated as a left parenthesis and $1$ as a right parenthesis. We show that binary words that are $7/3$-power-free have bounded nesting level, but this no longer holds for larger repetition exponents. We give an explicit characterization of the factors of the Thue-Morse word that are Dyck, and show how to count them. We also prove tight upper and lower bounds on $f(n)$, the number of Dyck factors of Thue-Morse of length $2n$., Comment: Full version of a paper to be submitted to WORDS 2023

A \emph{palindrome} is a word that reads the same forwards and backwards. A \emph{block palindrome factorization} (or \emph{BP-factorization}) is a factorization of a word into blocks that becomes palindrome if each identical block is replaced by a distinct symbol. We call the number of blocks in a BP-factorization the \emph{width} of the BP-factorization. The \emph{largest BP-factorization} of a word $w$ is the BP-factorization of $w$ with the maximum width. We study words with certain BP-factorizations. First, we give a recurrence for the number of length-$n$ words with largest BP-factorization of width $t$. Second, we show that the expected width of the largest BP-factorization of a word tends to a constant. Third, we give some results on another extremal variation of BP-factorization, the \emph{smallest BP-factorization}. A \emph{border} of a word $w$ is a non-empty word that is both a proper prefix and suffix of $w$. Finally, we conclude by showing a connection between words with a unique border and words whose smallest and largest BP-factorizations coincide.

The complement $\bar{x}$ of a binary word $x$ is obtained by changing each $0$ in $x$ to $1$ and vice versa. An antisquare is a nonempty word of the form $x\, \bar{x}$. In this paper, we study infinite binary words that do not contain arbitrarily large antisquares. For example, we show that the repetition threshold for the language of infinite binary words containing exactly two distinct antisquares is $(5+\sqrt{5})/2$. We also study repetition thresholds for related classes, where "two" in the previous sentence is replaced by a large number. We say a binary word is good if the only antisquares it contains are $01$ and $10$. We characterize the minimal antisquares, that is, those words that are antisquares but all proper factors are good. We determine the the growth rate of the number of good words of length $n$ and determine the repetition threshold between polynomial and exponential growth for the number of good words.

The complement $\overline{x}$ of a binary word $x$ is obtained by changing each $0$ in $x$ to $1$ and vice versa. We study infinite binary words $\bf w$ that avoid sufficiently large complementary factors; that is, if $x$ is a factor of $\bf w$ then $\overline{x}$ is not a factor of $\bf w$. In particular, we classify such words according to their critical exponents.

We generalize the familiar notion of periodicity in sequences to a new kind of pseudoperiodicity, and we prove some basic results about it. We revisit the results of a 2012 paper of Shevelev and reprove his results in a simpler and more unified manner, and provide a complete answer to one of his previously unresolved questions. We consider finding words with specific pseudoperiods and having the smallest possible critical exponent. Finally, we consider the problem of determining whether a finite word is pseudoperiodic of a given size, and show that it is NP-complete.

We disprove a 2002 conjecture of Dombi from additive number theory. More precisely, we find examples of sets $A \subset \mathbb{N}$ with the property that $\mathbb{N} \setminus A$ is infinite, but the sequence $n \rightarrow |\{ (a,b,c) \, : \, n=a+b+c \text{ and } a,b,c \in A \}|$, counting the number of $3$-compositions using elements of $A$ only, is strictly increasing., Comment: additional author added; largely rewritten with different example

In a recent talk of Robbert Fokkink, some conjectures related to the infinite Tribonacci word were stated by the speaker and the audience. In this note we show how to prove (or disprove) the claims easily in a "purely mechanical" fashion, using the Walnut theorem-prover.

First we reprove two results in additive number theory due to Dombi and Chen & Wang, respectively, on the number of representations of n as the sum of two odious or evil numbers, using techniques from automata theory and logic. We also use this technique to prove a new result about the numbers represented by five summands. Furthermore, we prove some new results on the tenfold sums of the evil and odious numbers, as well as k-fold sums of similar sequences of integers, by using techniques of analytic number theory involving trigonometric sums associated with the (+-1)-characteristic sequences of these integers., Revision of previous version, with new author and results added

We construct an infinite binary word with critical exponent 3 that avoids abelian 4-powers. Our method gives an algorithm to determine if certain types of morphic sequences avoid additive powers. We also show that there are $\Omega(1.172^n)$ binary words of length $n$ that avoid abelian 4-powers, which improves on previous estimates., Comment: 11 pages

We describe Hilbert's spacefilling curve in several different ways: as an automatic sequence of directions,as a regular and synchronized sequence of coordinates of lattice points encountered, and as an automatic bitmap image.

The Frobenius number $g(S)$ of a set $S$ of non-negative integers with $\gcd 1$ is the largest integer not expressible as a linear combination of elements of $S$. Given a sequence ${\bf s} = (s_i)_{i \geq 0}$, we can define the associated sequence $G_{\bf s} (i) = g(\{ s_i,s_{i+1},\ldots \})$. In this paper we compute $G_{\bf s} (i)$ for some classical automatic sequences: the evil numbers, the odious numbers, and the lower and upper Wythoff sequences. In contrast with the usual methods, our proofs are based largely on automata theory and logic.

We generalize Axel Thue's familiar definition of overlaps in words, and show that there are no infinite words containing split occurrences of these generalized overlaps. Along the way we prove a useful theorem about repeated disjoint occurrences in words -- an interesting natural variation on the classical de Bruijn sequences.

An overlap-free (or $��$-free) word $w$ over a fixed alphabet $��$ is extremal if every word obtained from $w$ by inserting a single letter from $��$ at any position contains an overlap (or a factor of exponent at least $��$, respectively). We find all lengths which admit an extremal overlap-free binary word. For every extended real number $��$ such that $2^+\leq��\leq 8/3$, we show that there are arbitrarily long extremal $��$-free binary words.

We show that it is decidable, given an automatic sequence $\bf s$ and a constant $c$, whether all prefixes of $\bf s$ have a string attractor of size $\leq c$. Using a decision procedure based on this result, we show that all prefixes of the period-doubling sequence of length $\geq 2$ have a string attractor of size $2$. We also prove analogous results for other sequences, including the Thue-Morse sequence and the Tribonacci sequence. We also provide general upper and lower bounds on string attractor size for different kinds of sequences. For example, if $\bf s$ has a finite appearance constant, then there is a string attractor for ${\bf s}[0..n-1]$ of size $O(\log n)$. If further $\bf s$ is linearly recurrent, then there is a string attractor for ${\bf s}[0..n-1]$ of size $O(1)$. For automatic sequences, the size of the smallest string attractor for ${\bf s}[0..n-1]$ is either $\Theta(1)$ or $\Theta(\log n)$, and it is decidable which case occurs. Finally, we close with some remarks about greedy string attractors., Comment: revision adding significant new results due to Luke Schaeffer

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 $x p(x)$, where $p$ is any permutation of the underlying alphabet, and $x t(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 $x h(x)$ for every nonerasing morphism $h$ and all sufficiently large words $x$.

In 2013, Fici and Zamboni proved a number of theorems about finite and infinite words having only a small number of factors that are palindromes. In this paper we rederive some of their results, and obtain some new ones, by a different method based on finite automata., Comment: Minor typo corrections

Rich words are characterized by 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 address 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 $\Sigma_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., Comment: 12 pages

The permutation language $P_n$ consists of all words that are permutations of a fixed alphabet of size $n$. Using divide-and-conquer, we construct a regular expression $R_n$ that specifies $P_n$. We then give explicit bounds for the length of $R_n$, which we find to be $4^n n^{-(\lg n)/4+\Theta(1)}$, and use these bounds to show that $R_n$ has minimum size over all regular expressions specifying $P_n$., Comment: 14 pages

We prove various results about the largest exponent of a repetition in a factor of the Thue-Morse word, when that factor is considered as a circular word. Our results confirm and generalize previous results of Fitzpatrick and Aberkane & Currie.

Let $x$ and $y$ be words. We consider the languages whose words $z$ are those for which the numbers of occurrences of $x$ and $y$, as subwords of $z$, are the same (resp., the number of $x$'s is less than the number of $y$'s, resp., is less than or equal). We give a necessary and sufficient condition on $x$ and $y$ for these languages to be regular, and we show how to check this condition efficiently.

We prove that the number of natural exact covering systems of cardinality $k$ is equal to the coefficient of $x^k$ in the reversion of the power series $\sum_{k \ge 1} ��(k) x^k$, where $��(k)$ is the usual number-theoretic M��bius function. Using this result, we deduce an asymptotic expression for the number of such systems.

We consider a natural generalization of the Nagell-Ljunggren equation to the case where the qth power of an integer y, for q >= 2, has a base-b representation that consists of a length-l block of digits repeated n times, where n >= 2. Assuming the abc conjecture of Masser and Oesterl��, we completely characterize those triples (q, n, l) for which there are infinitely many solutions b. In all cases predicted by the abc conjecture, we are able (without any assumptions) to prove there are indeed infinitely many solutions.

We determine the minimum possible critical exponent for all palindromes over finite alphabets.

We investigate the behavior of the periods and border lengths of random words over a fixed alphabet. We show that the asymptotic probability that a random word has a given maximal border length $k$ is a constant, depending only on $k$ and the alphabet size $\ell$. We give a recurrence that allows us to determine these constants with any required precision. This also allows us to evaluate the expected period of a random word. For the binary case, the expected period is asymptotically about $n-1.641$. We also give explicit formulas for the probability that a random word is unbordered or has maximum border length one.

We consider several novel aspects of unique factorization in formal languages. We reprove the familiar fact that the set uf(L) of words having unique factorization into elements of L is regular if L is regular, and from this deduce an quadratic upper and lower bound on the length of the shortest word not in uf(L). We observe that uf(L) need not be context-free if L is context-free. Next, we consider variations on unique factorization. We define a notion of "semi-unique" factorization, where every factorization has the same number of terms, and show that, if L is regular or even finite, the set of words having such a factorization need not be context-free. Finally, we consider additional variations, such as unique factorization "up to permutation" and "up to subset".

The Danish composer Per Noergaard defined the "infinity series" s = (s(n))_n>=0 by the rules s(0) = 0, s(2n) = -s(n) for n >= 1, and s(2n + 1) = s(n) + 1 for n >= 0; it figures prominently in many of his compositions. Here we give several new results about this sequence: first, the set of binary representations of the positions of each note forms a context-free language that is not regular; second, a complete characterization of exactly which note-pairs appear; third, that consecutive occurrences of identical phrases are widely separated. We also consider to what extent the infinity series is unique.

As is well-known, the ratio of adjacent Fibonacci numbers tends to phi = (1 + sqrt(5))/2, and the ratio of adjacent Tribonacci numbers (where each term is the sum of the three preceding numbers) tends to the real root eta of X^3 - X^2 - X - 1 = 0. Letting alpha(n) denote the corresponding ratio for the generalized Fibonacci numbers, where each term is the sum of the n preceding, we obtain rapidly converging series for alpha(n), 1/alpha(n), and 1/(2-alpha(n)).

In this paper we consider the following problems: how many different subsets of Sigma^n can occur as set of all length-n factors of a finite word? If a subset is representable, how long a word do we need to represent it? How many such subsets are represented by words of length t? For the first problem, we give upper and lower bounds of the form alpha^(2^n) in the binary case. For the second problem, we give a weak upper bound and some experimental data. For the third problem, we give a closed-form formula in the case where n

A palstar (after Knuth, Morris, and Pratt) is a concatenation of even-length palindromes. We show that, asymptotically, there are $\Theta(\alpha_k^n)$ palstars of length $2n$ over a $k$-letter alphabet, where $\alpha_k$ is a constant such that $2k-1 < \alpha_k < 2k-{1 \over 2}$. In particular, $\alpha_2 \doteq 3.33513193$.

We discuss the notion of privileged word, recently introduced by Peltomaki. A word w is privileged if it is of length =1, then w^j is privileged for all j >= 0; (2) the language of privileged words is neither regular nor context-free; (3) there is a linear-time algorithm to check if a given word is privileged; and (4) there are at least 2^{n-5}/n^2 privileged binary words of length n.

We investigate questions related to the presence of primitive words and Lyndon words in automatic and linearly recurrent sequences. We show that the Lyndon factorization of a k-automatic sequence is itself k-automatic. We also show that the function counting the number of primitive factors (resp., Lyndon factors) of length n in a k-automatic sequence is k-regular. Finally, we show that the number of Lyndon factors of a linearly recurrent sequence is bounded.

Currie and Saari initiated the study of least periods of infinite words, and they showed that every integer n >= 1 is a least period of the Thue-Morse sequence. We generalize this result to show that the characteristic sequence of least periods of a k-automatic sequence is (effectively) k-automatic. Through an implementation of our construction, we confirm the result of Currie and Saari, and we obtain similar results for the period-doubling sequence, the Rudin-Shapiro sequence, and the paperfolding sequence.

We show that the subword complexity function p_x(n), which counts the number of distinct factors of length n of a sequence x, is k-synchronized in the sense of Carpi if x is k-automatic. As an application, we generalize recent results of Goldstein. We give analogous results for the number of distinct factors of length n that are primitive words or powers. In contrast, we show that the function that counts the number of unbordered factors of length n is not necessarily k-synchronized for k-automatic sequences., Comment: Some new results and better exposition

Given a formal language L specified in various ways, we consider the problem of determining if L is nonempty. If L is indeed nonempty, we find upper and lower bounds on the length of the shortest string in L.

We give another proof of a theorem of Fife - understood broadly as providing a finite automaton that gives a complete description of all infinite binary overlap-free words. Our proof is significantly simpler than those in the literature. As an application we give a complete characterization of the overlap-free words that are 2-automatic.

In this note, we give a construction that provides a tight lower bound of mn-1 for the length of the shortest word in the intersection of two regular languages with state complexities m and n.

The classical Frobenius problem is to compute the largest number g not representable as a non-negative integer linear combination of non-negative integers x_1, x_2, ..., x_k, where gcd(x_1, x_2, ..., x_k) = 1. In this paper we consider generalizations of the Frobenius problem to the noncommutative setting of a free monoid. Unlike the commutative case, where the bound on g is quadratic, we are able to show exponential or subexponential behavior for an analogue of g, depending on the particular measure chosen., Comment: 19 pages; preliminary announcement

Brandenburg and (implicitly) Dejean introduced the concept of repetition threshold: the smallest real number alpha such that there exists an infinite word over a k-letter alphabet that avoids beta-powers for all beta>alpha. We generalize this concept to include the lengths of the avoided words. We give some conjectures supported by numerical evidence and prove one of these conjectures.

We examine words w satisfying the following property: if x is a subword of w and |x| is at least k for some fixed k, then the reversal of x is not a subword of w., Comment: 6 pages