The k -regular sequences form a large class studied in number theory, combinatorics, and other parts of discrete mathematics. This class is known to be closed under many natural operations, such as term-by-term sum, product, running sum, and so forth, but it is not closed under running maximum. Proving the previously-known counterexample, involving the Stern sequence, required intricate arguments. In this note, we construct a significantly simpler example of a k -regular sequence whose running maximum is not k -regular.

Mignosi, Restivo, and Salemi (1998) proved that for all ϵ > 0 there exists an integer N such that all prefixes of the Fibonacci word of length ≥ N contain a suffix of exponent α 2 − ϵ , where α = ( 1 + 5 ) / 2 is the golden ratio. In this note we show how to prove an explicit version of this theorem using tools from automata theory and logic. Along the way we gain a better understanding of the repetitive structure of the Fibonacci word.

We say a finite word x is a palindromic periodicity if there exist two palindromes p and s such that |x| ≥ |ps| and x is a prefix of the infinite periodic word (ps)^ω = pspsps⋯. In this paper we examine the palindromic periodicities occurring in some classical infinite words, such as Sturmian words, episturmian words, the Thue-Morse word, the period-doubling word, the Rudin-Shapiro word, the paperfolding word, and the Tribonacci word, and prove a number of results about them. We also prove results about words with the smallest number of distinct palindromic periodicities.

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.

We show that the first-order theory of Sturmian words over Presburger arithmetic is decidable. Using a general adder recognizing addition in Ostrowski numeration systems by Baranwal, Schaeffer and Shallit, we prove that the first-order expansions of Presburger arithmetic by a single Sturmian word are uniformly $\omega$-automatic, and then deduce the decidability of the theory of the class of such structures. Using an implementation of this decision algorithm called Pecan, we automatically reprove classical theorems about Sturmian words in seconds, and are able to obtain new results about antisquares and antipalindromes in characteristic Sturmian words.

Abstract. We construct an infinite binary word with critical exponent 3 that avoids abelian 4-powers. Our method gives an algorithm to determine whether certain types of morphic sequences avoid additive powers. We also show that there are [Formula: see text] binary words of length [Formula: see text] that avoid abelian 4-powers, which improves on previous estimates.

Venkatachala on the one hand, and Avdispahić & Zejnulahi on the other, both studied integer sequences with an unusual sum property defined in a greedy way, and proved many results about them. However, their proofs were rather lengthy and required numerous cases. In this paper, I provide a different approach, via finite automata, that can prove the same results (and more) in a simple, unified way. Instead of case analysis, we use a decision procedure implemented in the free software Walnut. Using these ideas, we can prove a conjecture of Quet and find connections between Quet's sequence and the “married” functions of Hofstadter.

The first-order theory of automatic sequences with addition is decidable, and this means that one can often prove combinatorial properties of these sequences "automatically", using the free software Walnut written by Hamoon Mousavi. In this talk I will explain how this is done, using as an example the measure of minimize size string attractor, introduced by Kempa and Prezza in 2018. Using the logic-based approach, we can also prove more general properties of string attractors for automatic sequences. This is joint work with Luke Schaeffer.

In this paper we consider a number of natural decision problems involving k-regular sequences. Specifically, they arise from considering lower and upper bounds on growth rate; in particular boundedness, images, regularity (recognizability by a deterministic finite automaton) of preimages, and factors, such as squares and palindromes,

We study the following natural variation on the classical universality problem: given a language $L(M)$ represented by $M$ (e.g., a DFA/RE/NFA/PDA), does there exist an integer $\ell \geq 0$ such that $Σ^\ell \subseteq L(M)$? In the case of an NFA, we show that this problem is NEXPTIME-complete, and the smallest such $\ell$ can be doubly exponential in the number of states. This particular case was formulated as an open problem in 2009, and our solution uses a novel and involved construction. In the case of a PDA, we show that it is recursively unsolvable, while the smallest such $\ell$ is not bounded by any computable function of the number of states. In the case of a DFA, we show that the problem is NP-complete, and $e^{\sqrt{n \log n} (1+o(1))}$ is an asymptotically tight upper bound for the smallest such $\ell$, where $n$ is the number of states. Finally, we prove that in all these cases, the problem becomes computationally easier when the length $\ell$ is also given in binary in the input: it is polynomially solvable for a DFA, PSPACE-complete for an NFA, and co-NEXPTIME-complete for a PDA.

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+Θ(1)}$, and use these bounds to show that $R_n$ has minimum size over all regular expressions specifying $P_n$.

A rollercoaster is a sequence of real numbers for which every maximal contiguous subsequence---increasing or decreasing---has length at least three. By translating this sequence to a set of points in the plane, a rollercoaster can be defined as an $x$-monotone polygonal path for which every maximal subpath, with positive- or negative-slope edges, has at least three vertices. Given a sequence of distinct real numbers, the rollercoaster problem asks for a maximum-length (not necessarily contiguous) subsequence that is a rollercoaster. It was conjectured that every sequence of $n$ distinct real numbers contains a rollercoaster of length at least $\lceil n/2\rceil$ for $n>7$, while the best known lower bound is $\Omega(n/\log n)$. In this paper we prove this conjecture. Our proof is constructive and implies a linear-time algorithm for computing a rollercoaster of this length. Extending the $O(n\log n)$-time algorithm for computing a longest increasing subsequence, we show how to compute a maximum-length rollercoaster within the same time bound. A maximum-length rollercoaster in a permutation of $\{1,\dots,n\}$ can be computed in $O(n\log\log n)$ time. The search for rollercoasters was motivated by the orthogeodesic point-set embedding of caterpillars. A caterpillar is a tree such that deleting the leaves gives a path, called the spine. A top-view caterpillar is an embedded caterpillar where every vertex has degree either 4 or 1 and such that the two leaves adjacent to each spine vertex lie on opposite sides of the spine. As an application of our result on rollercoasters, we are able to find a planar drawing of every $n$-vertex top-view caterpillar on every set of $\frac{25}{3}(n+4)$ points in the plane, such that each edge is an orthogonal path with one bend. This improves the previous best known upper bound on the number of required points, which is $O(n\log n)$. We also show that such a drawing can be obtained in linear time when the points are given in sorted order.

A rollercoaster is a sequence of real numbers for which every maximal contiguous subsequence, that is increasing or decreasing, has length at least three. By translating this sequence to a set of points in the plane, a rollercoaster can be defined as a polygonal path for which every maximal sub-path, with positive- or negative-slope edges, has at least three points. Given a sequence of distinct real numbers, the rollercoaster problem asks for a maximum-length subsequence that is a rollercoaster. It was conjectured that every sequence of $n$ distinct real numbers contains a rollercoaster of length at least $\lceil n/2\rceil$ for $n>7$, while the best known lower bound is $Ω(n/\log n)$. In this paper we prove this conjecture. Our proof is constructive and implies a linear-time algorithm for computing a rollercoaster of this length. Extending the $O(n\log n)$-time algorithm for computing a longest increasing subsequence, we show how to compute a maximum-length rollercoaster within the same time bound. A maximum-length rollercoaster in a permutation of $\{1,\dots,n\}$ can be computed in $O(n \log \log n)$ time. The search for rollercoasters was motivated by orthogeodesic point-set embedding of caterpillars. A caterpillar is a tree such that deleting the leaves gives a path, called the spine. A top-view caterpillar is one of degree 4 such that the two leaves adjacent to each vertex lie on opposite sides of the spine. As an application of our result on rollercoasters, we are able to find a planar drawing of every $n$-node top-view caterpillar on every set of $\frac{25}{3}n$ points in the plane, such that each edge is an orthogonal path with one bend. This improves the previous best known upper bound on the number of required points, which is $O(n \log n)$. We also show that such a drawing can be obtained in linear time, provided that the points are given in sorted order.

We show how to prove theorems in additive number theory using a decision procedure based on finite automata. Among other things, we obtain the following analogue of Lagrange's theorem: every natural number > 686 is the sum of at most 4 natural numbers whose canonical base-2 representation is a binary square, that is, a string of the form xx for some block of bits x. Here the number 4 is optimal. While we cannot embed this theorem itself in a decidable theory, we show that stronger lemmas that imply the theorem can be embedded in decidable theories, and show how automated methods can be used to search for these stronger lemmas.

Recently, Cilleruelo, Luca, & Baxter proved, for all bases b >= 5, that every natural number is the sum of at most 3 natural numbers whose base-b representation is a palindrome. However, the cases b = 2, 3, 4 were left unresolved. We prove, using a decision procedure based on automata, that every natural number is the sum of at most 4 natural numbers whose base-2 representation is a palindrome. Here the constant 4 is optimal. We obtain similar results for bases 3 and 4, thus completely resolving the problem.

A rectifier network is a directed acyclic graph with distinguished sources and sinks; it is said to compute a Boolean matrix M that has a 1 in the entry (i,j) iff there is a path from the j-th source to the i-th sink. The smallest number of edges in a rectifier network that computes M is a classic complexity measure on matrices, which has been studied for more than half a century. We explore two techniques that have hitherto found little to no applications in this theory. They build upon a basic fact that depth-2 rectifier networks are essentially weighted coverings of Boolean matrices with rectangles. Using fractional and greedy coverings (defined in the standard way), we obtain new results in this area. First, we show that all fractional coverings of the so-called full triangular matrix have cost at least n log n. This provides (a fortiori) a new proof of the tight lower bound on its depth-2 complexity (the exact value has been known since 1965, but previous proofs are based on different arguments). Second, we show that the greedy heuristic is instrumental in tightening the upper bound on the depth-2 complexity of the Kneser-Sierpinski (disjointness) matrix. The previous upper bound is O(n^{1.28}), and we improve it to O(n^{1.17}), while the best known lower bound is Omega(n^{1.16}). Third, using fractional coverings, we obtain a form of direct product theorem that gives a lower bound on unbounded-depth complexity of Kronecker (tensor) products of matrices. In this case, the greedy heuristic shows (by an argument due to Lovász) that our result is only a logarithmic factor away from the "full" direct product theorem. Our second and third results constitute progress on open problem 7.3 and resolve, up to a logarithmic factor, open problem 7.5 from a recent book by Jukna and Sergeev (in Foundations and Trends in Theoretical Computer Science (2013)).

A \itbf{cover} of a string $x = x[1..n]$ is a proper substring $u$ of $x$ such that $x$ can be constructed from possibly overlapping instances of $u$. A recent paper \cite{FIKPPST13} relaxes this definition --- an \itbf{enhanced cover} $u$ of $x$ is a border of $x$ (that is, a proper prefix that is also a suffix) that covers a {\it maximum} number of positions in $x$ (not necessarily all) --- and proposes efficient algorithms for the computation of enhanced covers. These algorithms depend on the prior computation of the \itbf{border array} $β[1..n]$, where $β[i]$ is the length of the longest border of $x[1..i]$, $1 \le i \le n$. In this paper, we first show how to compute enhanced covers using instead the \itbf{prefix table}: an array $π[1..n]$ such that $π[i]$ is the length of the longest substring of $x$ beginning at position $i$ that matches a prefix of $x$. Unlike the border array, the prefix table is robust: its properties hold also for \itbf{indeterminate strings} --- that is, strings defined on {\it subsets} of the alphabet $Σ$ rather than individual elements of $Σ$. Thus, our algorithms, in addition to being faster in practice and more space-efficient than those of \cite{FIKPPST13}, allow us to easily extend the computation of enhanced covers to indeterminate strings. Both for regular and indeterminate strings, our algorithms execute in expected linear time. Along the way we establish an important theoretical result: that the expected maximum length of any border of any prefix of a regular string $x$ is approximately 1.64 for binary alphabets, less for larger ones.

A length n word is (palindromic) rich if it contains the maximum possible number, which is n , of distinct non-empty palindromic factors. We prove both necessary and sufficient conditions for richness in terms of run-length encodings of words. Relating sufficient conditions to integer partitions, we prove a lower bound of order C n , where C ≈ 37.6 , on the growth function of the language of binary rich words. From experimental study we suggest that this growth function actually grows more slowly than n n , which makes our lower bound quite reasonable.

We show that there exists an infinite word over the alphabet {0, 1, 3, 4} containing no three consecutive blocks of the same size and the same sum. This answers an open problem of Pirillo and Varricchio from 1994.

A filtration of a formal language L by a sequence s maps L to the set of words formed by taking the letters of words of L indexed only by s. We consider the languages resulting from filtering by all arithmetic progressions. If L is regular, it is easy to see that only finitely many distinct languages result; we give bounds on the number of distinct languages in terms of the state complexity of L. By contrast, there exist CFL's that give infinitely many distinct languages as a result. We use our technique to show that two related operations, including diag (which extracts the diagonal of words of square length arranged in a square array), preserve regularity but do not preserve context-freeness.

In this paper we consider the computational complexity of the following problems: given a DFA or NFA representing a regular language L over a finite alphabet Σ, is the set of all prefixes (resp., suffixes, factors, subwords) of all words of L equal t

The classical Frobenius problem over ${mathbb N}$ is to compute the largest integer $g$ not representable as a non-negative integer linear combination of non-negative integers $x_1, x_2, ldots, x_k$, where $gcd(x_1, x_2, ldots, x_k) = 1$. In this paper we consider novel 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 several analogues of $g$, with the precise bound depending on the particular measure chosen.

In this paper we consider the computational complexity of some problems dealing with matrix rank. Let E, S be subsets of a commutative ring R. Let x1, x2, ..., x t be variables. Given a matrix M= M(x1, x2, ..., x t ) with entries chosen from E ∪ {x1, x2, ..., x t }, we want to determine $$\max rank_S (M) = \mathop {max}\limits_{(a_1 ,a_2 ,...a_t ) \in S^t } rank M(a_1 ,a_2 ,...a_t )$$ and $$\min rank_S (M) = \mathop {min}\limits_{(a_1 ,a_2 ,...a_t ) \in S^t } rank M(a_1 ,a_2 ,...a_t ).$$There are also variants of these problems that specify more about the structure of M, or instead of asking for the minimum or maximum rank, ask if there is some substitution of the variables that makes the matrix invertible or noninvertible.Depending on E, S, and on which variant is studied, the complexity of these problems can range from polynomial-time solvable to random polynomial-time solvable to NP-complete to PSPACE-solvable to unsolvable.

We study the worst-case behavior of three iterative algorithms for computing the Jacobi symbol (vu). Each algorithm is similar in format to the Euclidean algorithm for computing gcd(u, v). Eisenstein's algorithm chooses an even quotient at each step. It is shown that the worst case occurs when u = 2n + 1, v = 2n − 1. Lebesgue's algorithm is essentially the least-remainder Euclidean algorithm with powers of 2 removed at each step. Its worst case occurs when u = 2Ln − Ln − 1, v = Ln, where L0 = 1, L1 = 1, and Ln = 2Ln − 1 + Ln − 2 for n ≥ 2. The “ordinary” Jacobi symbol algorithm is essentially the ordinary Euclidean algorithm with powers of 2 removed at each step. It is the most interesting mathematically of the three. We prove that if the ordinary algorithm on input (u, v) performs n division steps, with u>v>0 and u + v as small as possible, then u = An and v = An − 1, where A0 = 1, A1 = 3, A2n = A2n − 1 + 2A2n − 2 for n ≥ 1, and A2n+1 = 2A2n + A2n − 1 for n ≥ 1. We also discuss the worst-case inputs to the ordinary algorithm under the lexicographic and reverse lexicographic orderings.

In this note we give two methods for generating images of (approximations to) fractals and fractal-like sets: iterated Kronecker products and iterated matrix-valued homomorphisms. In contrast to the well-known methods for vector displays, the methods generate rectangular arrays of intensity levels which are particularly suited to display on raster devices with bitmap capabilities. The methods also give efficient parallel algorithms for computing n × n images, which require O(log n) operations per pixel.

Let $w \in (0 + 1)^*$ be a finite nonempty string of zeros and ones, and let $a_w (n)$ denote the number of (possibly overlapping) occurrences of w in the binary expansion of n. Allouche and Shallit have recently shown that there exists an effectively computable rational function $b_w (n)$ such that \[ \sum_{n\geqq 0} \log_2 (b_w (n))X^{a_w (n)} = \frac{1}{X - 1} \] for all complex X such that $| X |\leqq 1$ and $X \ne 1$. They gave an algorithm to determine $b_w (n)$. It is shown that the algorithm to determine $b_w (n)$ is related to a certain labeled binary tree $T(w)$. This observation allows two identities to be proven for the rational functions $b_w (n)$. Combinatorial methods are used to investigate the structure of the tree $T(w)$. As the running time of the algorithm is proportional to the total number of nodes in the tree $T(w)$, the algorithm in this paper is shown to run in polynomial time by proving that $|T(w)| =O(|w|^{11.1})$. The existence of infinitely many strings w such that $| T(w) |\geqq c| w |^3 $ is also shown.

Let N be a positive integer, and let $\sigma (N)$ denote the sum of the divisors of N (e.g. $\sigma (6) = 1 + 2 + 3 + 6 = 12$). We show computing $\sigma (N)$ is equivalent to factoring N in the following sense: there is a random polynomial time algorithm that, given $\sigma (N)$, produces the prime factorization of N, and $\sigma (N)$ can be computed in polynomial time given the factorization of N. We show that the same result holds for $\sigma _k (N)$, the sum of the kth powers of divisors of N We give three new examples of problems that are in Gill’s complexity class BPP: perfect numbers, multiply perfect numbers, and amicable pairs. These are the first “natural” sets in BPP that are not obviously in RP.

This paper discusses some new integer factoring methods involving cyclotomic polynomials. There are several polynomials f(X) known to have the following property: given a multiple of f(p), we can quickly split any composite number that has p as a prime divisor. For example -- taking f(X) to be X- 1 -- a multiple of p - 1 will suffice to easily factor any multiple of p, using an algorithm of Pollard. Other methods (due to Guy, Williams, and Judd) make use of X + 1, X2 + 1, and X2 ± X + 1. We show that one may take f to be Φk, the k-th cyclotomic polynomial. In constrast to the ad hoc methods used previously, we give a universal construction based on algebraic number theory that subsumes all the above results. Assuming generalized Riemann hypotheses, the expected time to factor N (given a multiple E of Φk(p)) is bounded by a polynomial in k, logE, and logN.

Let N be a positive integer, and let σ(N) denote the sum of the positive integral divisors of N. We show computing σ(N) is equivalent to factoring N in the following sense: there is a random polynomial time algorithm that, given σ(N), produces the prime factorization of N, and σ(N) can be easily computed given the factorization of N.