Author name cluster

Jeffrey Shallit

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

36 papers

1 author row

TCS Journal 2026 Journal Article

A self-generating sequence

Benoit Cloitre
Jeffrey Shallit

• Proves a conjecture from 2009 about a self-generating sequence. • Connects the sequence to the well-known paperfolding sequence. • Uses automata theory and a theorem-prover, instead of the usual proofs by induction. In 2009 the first author introduced a certain self-generating sequence ( a n ) n ≥ 1 = 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 2, 2, …, with the property that the sum of the terms appearing in the n th run equals twice the n th term of the sequence. We give a connection between this sequence and the paperfolding sequence, and then prove a conjecture about the density of 1s appearing in ( a n ) n ≥ 1.

TCS Journal 2026 Journal Article

Computing the base-b representation of quadratic irrationals using automata

Aaron Barnoff
Curtis Bright
Jeffrey Shallit

We show that the nth digit of the base-b representation of any quadratic irrational α is a finite-state function of the Ostrowski α-representation of bn, and hence can be computed by a finite automaton. We use a satisfiability (SAT) solver to prove, for some quadratic irrationals, that the automata we construct are both minimal and unique. For other quadratic irrationals, the SAT solver is able to find smaller automata computing the digits of the irrational up to a high precision. We conjecture in these cases that the automata found do indeed compute all digits of the irrational correctly. We give a heuristic argument for this conjecture, though we leave this as an open question.

TCS Journal 2026 Journal Article

Prefixes of the Fibonacci word

Jeffrey Shallit

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.

TCS Journal 2026 Journal Article

State complexity of the minimal star basis

Jozef Jirásek
Galina Jirásková
Jeffrey Shallit

We determine the state complexity of the twooperations L → L L + and L → L ∖ L L +. For languages not containing the empty string, the latter is of interest because L ∖ L L + is the “minimal star basis”, the set of all strings of L that cannot be written as the concatenation of shorter strings of L, a concept first studied by John Brzozowski in 1966. Then, we use these results to get the state complexity of the minimal star basis of languages that do contain the empty string. We show that the complexity of minimal star basis for languages containing the empty string is greater than for those without it, providing that an input alphabet has at least three symbols. However, in the unary case, the relation between the state complexities of minimal star basis on these two classes of languages is the opposite.

TCS Journal 2024 Journal Article

Proving properties of some greedily-defined integer recurrences via automata theory

Jeffrey Shallit

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.

TCS Journal 2022 Journal Article

Computational aspects of sturdy and flimsy numbers

Trevor Clokie
Thomas F. Lidbetter
Antonio Molina Lovett
Jeffrey Shallit
Leon Witzman

Following Stolarsky, we say that a natural number n is flimsy in base b if some positive multiple of n has smaller digit sum in base b than n does; otherwise it is sturdy. When n is proven flimsy by multiplier k, we say n is k-flimsy. We study computational aspects of sturdy and flimsy numbers. We provide some criteria for determining whether a number is sturdy. We study the computational problem of checking whether a given number is sturdy, giving several algorithms for the problem, focusing particularly on the case b = 2. We find two additional, previously unknown sturdy primes. We develop a method for determining which numbers with a fixed number of 0's in binary are flimsy. Finally, we develop a method that allows us to estimate the number of k-flimsy numbers with n bits, and we provide explicit results for k = 3 and k = 5. Our results demonstrate the utility (and fun) of creating algorithms for number theory problems, based on methods of automata theory.

TCS Journal 2022 Journal Article

Decidability and k-regular sequences

Daniel Krenn
Jeffrey Shallit

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, of such sequences. We show that these decision problems are undecidable.

TCS Journal 2022 Journal Article

Lie complexity of words

Jason P. Bell
Jeffrey Shallit

Given a finite alphabet Σ and a right-infinite word w over Σ, we define the Lie complexity function L w: N → N, whose value at n is the number of conjugacy classes (under cyclic shift) of length-n factors x of w with the property that every element of the conjugacy class appears in w. We show that the Lie complexity function is uniformly bounded for words with linear factor complexity. As a result, we show that words of linear factor complexity have at most finitely many primitive factors y with the property that y n is again a factor for every n. We then look at automatic sequences and show that the Lie complexity function of a k-automatic sequence is also k-automatic.

I&C Journal 2022 Journal Article

Maximal state complexity and generalized de Bruijn words

Daniel Gabric
Štěpán Holub
Jeffrey Shallit

We compute the exact maximum state complexity for the language consisting of m words of length N, and characterize languages achieving the maximum. We also consider a special case, namely languages C ( w ) consisting of the conjugates of a single word w. The words for which the maximum state complexity of C ( w ) is achieved turn out to be a natural generalization of de Bruijn words. We show that generalized de Bruijn words exist for each length and consider the number of them.

TCS Journal 2022 Journal Article

Properties of a class of Toeplitz words

Gabriele Fici
Jeffrey Shallit

We study the properties of the uncountable set of Stewart words. These are Toeplitz words specified by infinite sequences of Toeplitz patterns of the form αβγ, where α, β, γ is any permutation of the symbols 0, 1, ?. We determine the critical exponent of the Stewart words, prove that they avoid the pattern x x y y x x, find all factors that are palindromes, and determine their subword complexity. An interesting aspect of our work is that we use automata-theoretic methods and a decision procedure for automata to carry out the proofs.

TCS Journal 2021 Journal Article

Ostrowski-automatic sequences: Theory and applications

Aseem Baranwal
Luke Schaeffer
Jeffrey Shallit

We extend the notion of k-automatic sequences to Ostrowski-automatic sequences, and develop a procedure to computationally decide certain combinatorial and enumeration questions about such sequences that can be expressed as predicates in first-order logic. Our primary contribution is the design and implementation of an adder recognizing addition in a generalized Ostrowski numeration system. We also provide applications of our work to several topics in combinatorics on words, including repetitions and pattern avoidance. We partially resolve a previous conjecture about balanced words by Rampersad et al. , and make the first progress on an open problem on rich words by Vesti. We also prove some known results about Lucas words using only machine computation.

TCS Journal 2019 Journal Article

Critical exponents of infinite balanced words

Narad Rampersad
Jeffrey Shallit
Élise Vandomme

Over an alphabet of size 3 we construct an infinite balanced word with critical exponent 2 + 2 / 2. Over an alphabet of size 4 we construct an infinite balanced word with critical exponent ( 5 + 5 ) / 4. Over larger alphabets, we give some candidates for balanced words (found computationally) having small critical exponents. We also explore a method for proving these results using the automated theorem prover Walnut.

TCS Journal 2019 Journal Article

Subword complexity and power avoidance

Jeffrey Shallit
Arseny Shur

We begin a systematic study of the relations between subword complexity of infinite words and their power avoidance. Among other things, we show that – the Thue–Morse word has the minimum possible subword complexity over all overlap-free binary words and all ( 7 3 ) -power-free binary words, but not over all ( 7 3 ) + -power-free binary words; – the twisted Thue–Morse word has the maximum possible subword complexity over all overlap-free binary words, but no word has the maximum subword complexity over all ( 7 3 ) -power-free binary words; – if some word attains the minimum possible subword complexity over all square-free ternary words, then one such word is the ternary Thue word; – the recently constructed 1-2-bonacci word has the minimum possible subword complexity over all symmetric square-free ternary words.

TCS Journal 2019 Journal Article

The number of valid factorizations of Fibonacci prefixes

Pierre Bonardo
Anna E. Frid
Jeffrey Shallit

We establish several recurrence relations and an explicit formula for V ( n ), the number of factorizations of the length-n prefix of the Fibonacci word into a (not necessarily strictly) decreasing sequence of standard Fibonacci words. In particular, we show that the sequence V ( n ) is the shuffle of the ceilings of two linear functions of n.

Highlights Conference 2018 Conference Abstract

Finite Automata and Additive Number Theory

Jeffrey Shallit

ABSTRACT. Additive number theory is the study of the additive properties of sets of natural numbers. One of the most famous results in this field is Lagrange's theorem from 1770: every natural number is the sum of four squares. In this talk I will show how logic and finite automata can be used to mechanically construct proofs of theorems in additive number theory of genuine interest to number theorists. For example, we can prove that every natural number is the sum of four binary palindromes (numbers whose base-2 representation reads the same forwards and backwards). I will give examples of what can be proven use this idea, mention some open problems, and talk about future applications and limitations. This represents joint work with Jason Bell, Dirk Nowotka, Tim Smith, Aayush Rajasekaran, Finn Lidbetter, P. Madhusudan, Kathryn Hare, Daniel Kane, and Carlo Sanna.

TCS Journal 2017 Journal Article

Abelian-square-rich words

Gabriele Fici
Filippo Mignosi
Jeffrey Shallit

An abelian square is the concatenation of two words that are anagrams of one another. A word of length n can contain at most Θ ( n 2 ) distinct factors, and there exist words of length n containing Θ ( n 2 ) distinct abelian-square factors, that is, distinct factors that are abelian squares. This motivates us to study infinite words such that the number of distinct abelian-square factors of length n grows quadratically with n. More precisely, we say that an infinite word w is abelian-square-rich if, for every n, every factor of w of length n contains, on average, a number of distinct abelian-square factors that is quadratic in n; and uniformly abelian-square-rich if every factor of w contains a number of distinct abelian-square factors that is proportional to the square of its length. Of course, if a word is uniformly abelian-square-rich, then it is abelian-square-rich, but we show that the converse is not true in general. We prove that the Thue–Morse word is uniformly abelian-square-rich and that the function counting the number of distinct abelian-square factors of length 2n of the Thue–Morse word is 2-regular. As for Sturmian words, we prove that a Sturmian word s α of angle α is uniformly abelian-square-rich if and only if the irrational α has bounded partial quotients, that is, if and only if s α has bounded exponent.

TCS Journal 2017 Journal Article

Decision algorithms for Fibonacci-automatic words, II: Related sequences and avoidability

Chen Fei Du
Hamoon Mousavi
Eric Rowland
Luke Schaeffer
Jeffrey Shallit

We use a decision procedure for the “Fibonacci-automatic” words to solve problems about a number of different sequences. In particular, we prove that there exists an aperiodic infinite binary word avoiding the pattern x x x R. This is the first avoidability result concerning a nonuniform morphism proven purely mechanically.

I&C Journal 2011 Journal Article

Decision problems for convex languages

Janusz Brzozowski
Jeffrey Shallit
Zhi Xu

We examine decision problems for various classes of convex languages, previously studied by Ang and Brzozowski, originally under the name “continuous languages”. We can decide whether a language L is prefix-, suffix-, factor-, or subword-convex in polynomial time if L is represented by a DFA, but these problems become PSPACE-complete if L is represented by an NFA. If a regular language is not convex, we find tight upper bounds on the length of the shortest words demonstrating this fact, in terms of the number of states of an accepting DFA. Similar results are proved for some subclasses of convex languages: the prefix-, suffix-, factor-, and subword-closed languages, and the prefix-, suffix-, factor-, and subword-free languages. Finally, we briefly examine these questions where L is represented by a context-free grammar.

TCS Journal 2009 Journal Article

Decimations of languages and state complexity

Dalia Krieger
Avery Miller
Narad Rampersad
Bala Ravikumar
Jeffrey Shallit

Let the words of a language L be arranged in increasing radix order: L = { w 0, w 1, w 2, … }. We consider transformations that extract terms from L in an arithmetic progression. For example, two such transformations are even ( L ) = { w 0, w 2, w 4 … } and odd ( L ) = { w 1, w 3, w 5, … }. Lecomte and Rigo observed that if L is regular, then so are even ( L ), odd ( L ), and analogous transformations of L. We find good upper and lower bounds on the state complexity of this transformation. We also give an example of a context-free language L such that even ( L ) is not context-free.

I&C Journal 2009 Journal Article

Detecting palindromes, patterns and borders in regular languages

Terry Anderson
John Loftus
Narad Rampersad
Nicolae Santean
Jeffrey Shallit

Given a language L and a non-deterministic finite automaton M, we consider whether we can determine efficiently (in the size of M) if M accepts at least one word in L, or infinitely many words. Given that M accepts at least one word in L, we consider how long a shortest word can be. The languages L that we examine include the palindromes, the non-palindromes, the k-powers, the non-k-powers, the powers, the non-powers (also called primitive words), the words matching a general pattern, the bordered words, and the unbordered words.

TCS Journal 2009 Journal Article

Efficient enumeration of words in regular languages

Margareta Ackerman
Jeffrey Shallit

The cross-section enumeration problem is to list all words of length n in a regular language L in lexicographical order. The enumeration problem is to list the first m words in L according to radix order. We present an algorithm for the cross-section enumeration problem that is linear in n + t, where t is the output size. We provide a detailed analysis of the asymptotic running time of our algorithm and that of known algorithms for both enumeration problems. We discuss some shortcomings of the enumeration algorithm found in the Grail computation package. In the practical domain, we modify Mäkinen’s enumeration algorithm to get an algorithm that is usually the most efficient in practice. We performed an extensive performance analysis of the new and previously known enumeration and cross-section enumeration algorithms and found when each algorithm is preferable.

TCS Journal 2009 Journal Article

On NFAs where all states are final, initial, or both

Jui-Yi Kao
Narad Rampersad
Jeffrey Shallit

We examine questions involving nondeterministic finite automata where all states are final, initial, or both initial and final. First, we prove hardness results for the nonuniversality and inequivalence problems for these NFAs. Next, we characterize the languages accepted. Finally, we discuss some state complexity problems involving such automata.

TCS Journal 2009 Journal Article

Periodicity, repetitions, and orbits of an automatic sequence

Jean-Paul Allouche
Narad Rampersad
Jeffrey Shallit

We revisit a technique of S. Lehr on automata and use it to prove old and new results in a simple way. We give a very simple proof of the 1986 theorem of Honkala that it is decidable whether a given k -automatic sequence is ultimately periodic. We prove that it is decidable whether a given k -automatic sequence is overlap-free (or squarefree, or cubefree, etc.). We prove that the lexicographically least sequence in the orbit closure of a k -automatic sequence is k -automatic, and use this last result to show that several related quantities, such as the critical exponent, irrationality measure, and recurrence quotient for Sturmian words with slope α, have automatic continued fraction expansions if α does.

TCS Journal 2009 Journal Article

State complexity of unique rational operations

Narad Rampersad
Nicolae Santean
Jeffrey Shallit
Bala Ravikumar

For each basic language operation we define its “unique” counterpart as being the operation that results in a language whose words can be obtained uniquely through the given operation. These unique operations can arguably be viewed as combined basic operations, placing this work in the popular area of state complexity of combined operations on regular languages. We study the state complexity of unique rational operations and we provide upper bounds and empirical results meant to cast light into this matter. Equally important, we hope to have provided a generic methodology for estimating their state complexity.

TCS Journal 2008 Journal Article

Words avoiding repetitions in arithmetic progressions

Jui-Yi Kao
Narad Rampersad
Jeffrey Shallit
Manuel Silva

Carpi constructed an infinite word over a 4-letter alphabet that avoids squares in all subsequences indexed by arithmetic progressions of odd difference. We show a connection between Carpi’s construction and the paperfolding words. We extend Carpi’s result by constructing uncountably many words that avoid squares in arithmetic progressions of odd difference. We also construct infinite words avoiding overlaps and infinite words avoiding all sufficiently large squares in arithmetic progressions of odd difference. We use these words to construct labelings of the 2-dimensional integer lattice such that any line through the lattice encounters a squarefree (resp. overlapfree) sequence of labels.

TCS Journal 2007 Journal Article

Every real number greater than 1 is a critical exponent

Dalia Krieger
Jeffrey Shallit

We prove that for every real number α > 1 there exists an infinite word w over a finite alphabet such that α is the critical exponent of w.

TCS Journal 2005 Journal Article

A generalization of repetition threshold

Lucian Ilie
Pascal Ochem
Jeffrey Shallit

Brandenburg and (implicitly) Dejean introduced the concept of repetition threshold: the smallest real number α such that there exists an infinite word over a k-letter alphabet that avoids β -powers for all β > α. We generalize this concept to include the lengths of the avoided words. We give some conjectures supported by numerical evidence and prove some of these conjectures. As a consequence of one of our results, we show that the pattern ABCBABC is 2-avoidable. This resolves a question left open in Cassaigne's thesis.

TCS Journal 2005 Journal Article

Avoiding large squares in infinite binary words

Narad Rampersad
Jeffrey Shallit
Ming-wei Wang

We consider three aspects of avoiding large squares in infinite binary words. First, we construct an infinite binary word avoiding both cubes xxx and squares yy with | y | ⩾ 4; our construction is somewhat simpler than the original construction of Dekking. Second, we construct an infinite binary word avoiding all squares except 0 2, 1 2, and ( 01 ) 2; our construction is somewhat simpler than the original construction of Fraenkel and Simpson. In both cases, we also show how to modify our construction to obtain exponentially many words of length n with the given avoidance properties. Finally, we answer an open question of Prodinger and Urbanek from 1979 by demonstrating the existence of two infinite binary words, each avoiding arbitrarily large squares, such that their perfect shuffle has arbitrarily large squares.

TCS Journal 2003 Journal Article

Periodicity, morphisms, and matrices

Sabin Cautis
Filippo Mignosi
Jeffrey Shallit
Ming-wei Wang
Soroosh Yazdani

In 1965, Fine and Wilf proved the following theorem: if (f n ) n⩾0 and (g n ) n⩾0 are periodic sequences of real numbers, of period lengths h and k, respectively, and f n =g n for 0⩽n<h+k−gcd(h, k), then f n =g n for all n⩾0. Furthermore, the constant h+k−gcd(h, k) is best possible. In this paper, we consider some variations on this theorem. In particular, we study the case where f n ⩽g n instead of f n =g n. We also obtain generalizations to more than two periods. We apply our methods to a previously unsolved conjecture on iterated morphisms, the decreasing length conjecture: if h: Σ∗→Σ∗ is a morphism with |Σ|=n, and w is a word with |w|>|h(w)|>|h 2(w)|>⋯>|h k (w)|, then k⩽n.

TCS Journal 2003 Journal Article

The ring of k-regular sequences, II

Jean-Paul Allouche
Jeffrey Shallit

In this paper, we continue our study of k-regular sequences begun in 1992. We prove some new results, give many new examples from the literature, and state some open problems.

TCS Journal 2002 Journal Article

On two-sided infinite fixed points of morphisms

Jeffrey Shallit
Ming-wei Wang

Let Σ be a finite alphabet, and let h: Σ∗ →Σ∗ be a morphism. Finite and infinite fixed points of morphisms—i. e. , those words w such that h(w)=w—play an important role in formal language theory. Head characterized the finite fixed points of h, and later, Head and Lando characterized the one-sided infinite fixed points of h. Our paper has two main results. First, we complete the characterization of fixed points of morphisms by describing all two-sided infinite fixed points of h, for both the “pointed” and “unpointed” cases. Second, we completely characterize the solutions to the equation h(xy)=yx in finite words.

TCS Journal 1997 Journal Article

Automaticity II: Descriptional complexity in the unary case

Carl Pomerance
John Michael Robson
Jeffrey Shallit

Let Σ and Δ be finite alphabets, and let ƒ be a map from Σ∗ to Δ. Then the deterministic automaticity of ƒ, Aƒ(n), is defined to be the size of the minimum finite-state machine that correctly computes ƒ on all inputs of size </n. A similar definition applies to languages L. We denote the nondeterministic analogue (for languages L) of automaticity by n l (n). In a previous paper, Shallit and Breitbart examined the properties of this measure of descriptional complexity in the case ¦Σ|⩾ 2. In this paper, we continue the study of automaticity, focusing on the case where ¦Σ¦= 1. We prove that Aƒ(n)</n + 1 − [logℓn], where ℓ = ¦Δ¦. We also prove that Aƒ(n) > n − 2 logℓ n − 2 logℓ logℓ n for almost all functions ƒ. In the nondeterministic case, we show that there exists a c such that for almost all unary languages L, we have NL(n) > cn log n for all sufficiently large n. The proof is based on a new enumeration method for languages accepted by unary q-state NFAs. If L is not a regular language, then it follows from a result of Karp that lim supn→∞ AL(n) n ⩾ 1 2. We conjecture that L − 0∗, then this bound can be improved to (√5 − 1) 2. Finally, we give some lower bounds for nondeterministic automaticity for nonregular languages.

TCS Journal 1996 Journal Article

On the vector space of the automatic reals

Siegfried Lehr
Jeffrey Shallit
John Tromp

A sequence (a n ) n ⩾ 0 is said to be k-automatic if a n is a finite-state function of the base-k digits of n. We say a real number is (k, b)-automatic if its fractional part has a base-b expansion that forms a k-automatic sequence, and we denote the set of all such numbers as L(k, b). Lehr (Theoret. Comput. Sci. 108 (1993) 385–391) proved that L(k, b) forms a vector space over Q. In this paper we give a shortened version of the proof of Lehr's result and, answering a question of Bach, show that the dimension of the vector space L(k, b) is infinite. We also give an example of a transcendental number such that all of its positive powers are automatic. The proof requires examining the coefficient of X n in the formal power series (X + X 2 + X 4 + X 8 + …) r. Along the way we are led to examine several sequences of independent combinatorial interest. Finally, solving an open problem, we show that the automatic reals are not closed under (1) product; (2) squaring; and (3) reciprocal.

TCS Journal 1992 Journal Article

Pattern spectra, substring enumeration, and automatic sequences

Jean-Paul Allouche
Patrick Morton
Jeffrey Shallit

Let {S(n)} n⩾0 be an infinite sequence on {+1, −1}. In a previous paper, Morton and Mourant (1989) showed how to expand {S(n)} n⩾0 uniquely as a (possibly infinite) termwise product of certain special infinite sequences on {+1, −1}, called pattern sequences. Moreover, they characterized those sequences for which the expansion, or pattern spectrum, is finite. In this paper, we first give the expansion of a subsequence of the Prouhet-Thue-Morse sequence studied by Newman and Slater (1969 and 1975) and Coquet (1983). Then we characterize the sequences given by certain special infinite products. Next, we prove a general theorem characterizing the pattern spectrum when S is an automatic sequence in the sense of Cobham (1972) and Christol (1980). We also show how to deduce this theorem as the consequence of a purely language-theoretic result about enumeration of substrings. Finally, we prove that no sequence can be its own pattern spectrum.

TCS Journal 1992 Journal Article

The ring of k-regular sequences

Jean-Paul Allouche
Jeffrey Shallit

The automatic sequence is the central concept at the intersection of formal language theory and number theory. It was introduced by Cobham (1969, 1972), and has been extensively studied by Christol et al. (1980) and other writers. Since the range of automatic sequences is finite, however, their descriptive power is severely limited. In this paper, we generalize the concept of automatic sequence to the case where the sequence can take its values in a (possibly infinite) ring R; we call such sequences k-regular. (When R is finite, we obtain automatic sequences as a special case.) We argue that k-regular sequences provide a good framework for discussing many “naturally occurring” sequences, and we support this contention by exhibiting many examples of k-regular sequences from numerical analysis, topology, number theory, combinatorics, analysis of algorithms, and the theory of fractals. We investigate the closure properties of k-regular sequences. We prove that the set of k-regular sequences forms a ring under the operations of term-by-term addition and convolution. Hence, the set of associated formal power series in R[[X]] also forms a ring. We show how k-regular sequences are related to Z -rational formal series. We give a machine model for the k-regular sequences. We prove that all k-regular sequences can be computed quickly. Let the pattern sequence e P (n) count the number of occurrences of the pattern P in the base-k expansion of n. Morton and Mourant (1989) showed that every sequence over Z has a unique expansion as a sum of pattern sequences. We prove that this “Fourier” expansion maps k-regular sequences to k-regular sequences. [This can be viewed as a generalizaiton of results of Choffrut and Schützenberger (1988), and previous results of Allouche et al. (1992)]. In particular, the coefficients in the expansion of e p (an + b) form a k-automatic sequence. Many natural examples and some open problems are given.

TCS Journal 1988 Journal Article

A generalization of automatic sequences

Jeffrey Shallit

We generalize the uniform tag sequences of Cobham, which arise as images of fixed points of k-uniform homomorphisms, to the case where the homomorphism ϕ is not necessarily uniform, but rather satisfies the analogue of an algebraic equation. We show that these sequences coincide with 1. (a) the class of sequences accepted by a finite automaton with “generalized digits” as input, and 2. (b) generalizations of the “locally catenative formula” of Rozenberg and Lindenmayer. Examples include the infinite Fibonacci word, which is generated as the fixed point of the homomorphism ϕ(a) = ab, ϕ(b) = a, and sequences of Rauzy and De Bruijn.