Search

We present a short proof of Cobham’s theorem without using Kronecker’s approximation theorem, making it suitable for generalization beyond automatic sequences.

P systems were introduced more than two decades ago by Gheorghe Pǎun. They are known as nondeterministic maximally parallel computing models. Most of their variants are proved to be capable of solving NP problems in polynomial time. This work focuses on using neural-like P systems to simulate uniform sequential computing models. In particular, we consider a so-called Spiking Neural P module (SN P module) computing finite-state functions. We define and characterize a so-called (SN) P automatic sequence by SN P modules.

Automatic sequences such as the Thue–Morse sequence and the Rudin–Shapiro sequence are highly predictable and thus not suitable in cryptography. In particular, they have small expansion complexity....

In this paper, we prove a conjecture of Chen and Wen that the boundary sequence of an automatic sequence is also automatic. In particular, we study the boundary sequences of the generalized Cantor sequences, and give a complete characterization of the periodic boundary sequences. As an application, for a class of automatic sequences, we prove that their abelian complexities are also automatic.

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.

Although a lot of research has been done on the factor complexity (also called subword complexity) of morphic words obtained as fixed points of iterated morphisms, there has been little development in exploring algorithms that can efficiently compute their abelian complexity. The factor complexity counts the number of factors of a given length n, while the abelian complexity counts that number up to letter permutation. We propose and analyze a simple O ( n ) algorithm for quickly computing the exact abelian complexities for all indices from 1 up to n, when considering binary uniform morphisms. Using our algorithm we also analyze the structure in the abelian complexity for that class of morphisms. Our main result implies, in particular, that the infinite word over the alphabet { - 1 , 0 , 1 } constructed from the consecutive forward differences of the abelian complexity of a fixed point of a binary uniform morphism is in fact an automatic sequence with the same morphic length. Since the proof produces morphisms that typically contain many redundant letters, we present an efficient algorithm to eliminate them in order to simplify the morphisms and to see the patterns produced more clearly.

Let $p$ be a prime number and consider a $p$-automatic sequence ${\bf u}=(u_{n})_{n\in\N}$ and its generating function $U(X)=\sum_{n=0}^{\infty}u_{n}X^{n}\in\mathbb{F}_{p}[[X]]$. Moreover, let us suppose that $u_{0}=0$ and $u_{1}\neq 0$ and consider the formal power series $V\in\mathbb{F}_{p}[[X]]$ which is a compositional inverse of $U(X)$, i.e., $U(V(X))=V(U(X))=X$. In this note we initiate the study of arithmetic properties of the sequence of coefficients of the power series $V(X)$. We are mainly interested in the case when $u_{n}=t_{n}$, where $t_{n}=s_{2}(n)\pmod{2}$ and ${\bf t}=(t_{n})_{n\in\N}$ is the Prouhet-Thue-Morse sequence defined on the two letter alphabet $\{0,1\}$. More precisely, we study the sequence ${\bf c}=(c_{n})_{n\in\N}$ which is the sequence of coefficients of the compositional inverse of the generating function of the sequence ${\bf t}$. This sequence is clearly 2-automatic. We describe the sequence ${\bf a}$ characterizing solutions of the equation $c_{n}=1$. In particular, we prove that the sequence ${\bf a}$ is 2-regular. We also prove that an increasing sequence characterizing solutions of the equation $c_{n}=0$ is not $k$-regular for any $k$. Moreover, we present a result concerning some density properties of a sequence related to ${\bf a}$., Comment: 16 pages; revised version will appear in Discrete Mathematics

The notion of a k-automatic set of integers is well-studied. We develop a new notion - the k-automatic set of rational numbers - and prove basic properties of these sets, including closure properties and decidability., Comment: Previous version appeared in Proc. LATA 2012 conference

We study correlation estimates of automatic sequences (that is, sequences computable by finite automata) with polynomial phases. As a consequence, we provide a new class of good weights for classical and polynomial ergodic theorems, not coming themselves from dynamical systems. We show that automatic sequences are good weights in $L^2$ for polynomial averages and totally ergodic systems. For totally balanced automatic sequences (i.e., sequences converging to zero in mean along arithmetic progressions) the pointwise weighted ergodic theorem in $L^1$ holds. Moreover, invertible automatic sequences are good weights for the pointwise polynomial ergodic theorem in $L^r$, $r>1$., 31 pages

Extending the result of Allouche et al., we prove that for any k, the two-dimensional sequence (modulo 2) {|Δk(t)np|}n,p≥0 is 2-automatic. Moreover, we prove that the three-dimensional sequence (modulo 2) {|Δk(t)np|}n,p,k≥0 is 2-automatic.

We describe a technique for mechanically proving certain kinds of theorems in combinatorics on words, using finite automata and a software package for manipulating them. We illustrate our technique by applying it to (a) solve an open problem of Currie and Saari on the lengths of unbordered factors in the Thue-Morse sequence; (b) verify an old result of Prodinger and Urbanek on the regular paperfolding sequence; (c) find an explicit expression for the recurrence function for the Rudin-Shapiro sequence; and (d) improve the avoidance bound in Leech's squarefree sequence. We also introduce a new measure of infinite words called condensation and compute it for some famous sequences. We follow up on the study of Currie and Saari of least periods of infinite words. We show that the characteristic sequence of least periods of a k-automatic sequence is (effectively) k-automatic. We compute the least periods for several famous sequences. Many of our results were obtained by machine computations.

A recurrent 2-dimensional sequence a(m,n) is given by fixing particular sequences a(m,0), a(0,n) as initial conditions and a rule of recurrence a(m,n)=f(a(m,n-1),a(m-1,n-1),a(m-1,n)) for m,n>=1. We generalize this concept to an arbitrary number of dimensions and of predecessors. We give a criterion for a general n-dimensional recurrent sequence to be alternatively produced by an n-dimensional substitution - i.e. to be an automatic sequence. We show also that if the initial conditions are p-automatic and the rule of recurrence is an F"p-affine function, then the n-dimensional sequence is p-automatic. Consequently all such n-dimensional sequences can be also defined by n-dimensional substitution. Finally we show various positive examples, but also a 2-dimensional recurrent sequence which is not k-automatic for any k. As a byproduct we show that for polynomials f@?Q[X] with deg(f)>=2 and f(N)@?N, the characteristic sequence of the set f(N) is not k-automatic for any k.

Following up on a paper of Balamohan et al. [‘On the behavior of a variant of Hofstadter’s $q$-sequence’, J. Integer Seq. 10 (2007)], we analyze a variant of Hofstadter’s $Q$-sequence and show that its frequency sequence is 2-automatic. An automaton computing the sequence is explicitly given.

We show that various aspects of k-automatic sequences — such as having an unbordered factor of length n — are both decidable and effectively enumerable. As a consequence it follows that many related sequences are either k-automatic or k-regular. These include many sequences previously studied in the literature, such as the recurrence function, the appearance function, and the repetitivity index. We also give some new characterizations of the class of k-regular sequences. Many results extend to other sequences defined in terms of Pisot numeration systems.

We consider compact group generalizations T(n) of the Thue-Morse sequence and prove that the subsequence T(n2) is uniformly distributed with respect to a measure gv that is absolutely continuous with respect to the Haar measure. The proof is based on a proper generalization of the Fourier based method of Mauduit and Rivat in their study of the sum-of-digits function of squares to group representations.

The critical exponent of an infinite word is defined to be the supremum of the exponent of each of its factors. For k-automatic sequences, we show that this critical exponent is always either a rational number or infinite, and its value is computable. Our results also apply to variants of the critical exponent, such as the initial critical exponent of Berthe, Holton, and Zamboni and the Diophantine exponent of Adamczewski and Bugeaud. Our work generalizes or recovers previous results of Krieger and others, and is applicable to other situations; e.g., the computation of the optimal recurrence constant for a linearly recurrent k-automatic sequence., In Proceedings WORDS 2011, arXiv:1108.3412

An infinite word is S-automatic if, for all n ≥ 0, its (n + 1)st letter is the output of a deterministic automaton fed with the representation of n in the considered numeration system S. In this extended abstract, we consider an analogous definition in a multidimensional setting and present the connection to the shape-symmetric infinite words introduced by Arnaud Maes. More precisely, for d ≥ 2, we state that a multidimensional infinite word x : N → Σ over a finite alphabet Σ is S-automatic for some abstract numeration system S built on a regular language containing the empty word if and only if x is the image by a coding of a shape-symmetric infinite word.

We consider extensions and restrictions of Wythoff's game having exactly the same set of P positions as the original game. No strict subset of rules gives the same set of P positions. On the other hand, we characterize all moves that can be adjoined while preserving the original set of P positions. Testing if a move belongs to such an extended set of rules is shown to be doable in polynomial time. Many arguments rely on the infinite Fibonacci word, automatic sequences and the corresponding numeration system. With these tools, we provide new two-dimensional morphisms generating an infinite picture encoding respectively P positions of Wythoff's game and moves that can be adjoined.

A pure morphic sequence is a right-infinite, symbolic sequence obtained by iterating a letter-to-word substitution. For instance, the Fibonacci sequence and the Thue–Morse sequence, which play an important role in theoretical computer science, are pure morphic. Define a coding as a letter-to-letter substitution. The image of a pure morphic sequence under a coding is called a morphic sequence.A sequence x is called uniformly recurrent if for each finite subword u of x there exists an integer l such that u occurs in every l-length subword of x.The paper mainly focuses on the problem of deciding whether a given morphic sequence is uniformly recurrent. Although the status of the problem remains open, we show some evidence for its decidability: in particular, we prove that it can be solved in polynomial time on pure morphic sequences and on automatic sequences.In addition, we prove that the complexity of every uniformly recurrent, morphic sequence has at most linear growth: here, complexity is understood as the function that maps each positive integer n to the number of distinct n-length subwords occurring in the sequence.

Consider a nonstandard numeration system like the one built over the Fibonacci sequence where nonnegative integers are represented by words over {0,1} without two consecutive 1. Given a set X of integers such that the language of their greedy representations in this system is accepted by a finite automaton, we consider the problem of deciding whether or not X is a finite union of arithmetic progressions. We obtain a decision procedure for this problem, under some hypothesis about the considered numeration system. In a second part, we obtain an analogous decision result for a particular class of abstract numeration systems built on an infinite regular language.

In this paper, we prove that a class of regular sequences can be viewed as projections of fixed points of uniform morphisms on a countable alphabet, and also can be generated by countable states automata. Moreover, we prove that the regularity of some regular sequences is invariant under some codings., Comment: 10 pages

In this paper, we study the abelian complexity of the Rudin-Shapiro sequence and a related sequence. We show that these two sequences share the same complexity function $\rho(n)$ which satisfies certain recurrence relations. As a consequence, the abelian complexity function is $2$-regular. Further, we prove that the box dimension of the graph of the asymptotic function $\lambda(x)$ is $3/2$ where $\lambda(x)=\lim_{k\to\infty}\rho(4^{k}x)/\sqrt{4^{k}x}$ and $\rho(x)=\rho(\lfloor x\rfloor)$ for any $x> 0$., Comment: 18 pages, 1 figure

We extend a result of J.-P. Allouche and O. Salon on linear independence of formal power series associated to polynomial extractions of quasistrongly p-additive sequences. The original result was on the Fp-linear independence and we extend it to the Fp[X]-linear independence.

We obtain simple relations between the Hankel determinants of the formal power series ∏k≥0(1 + Jx3k) where [Formula: see text], and prove that the sequence of Hankel determinants is an aperiodic automatic sequence taking value in {±1, ±J, ±J2}. This research is essentially inspired by the works about Hankel determinants of Thue–Morse-like sequences by Allouche, Peyrière, Wen and Wen (1998), Bacher (2006) and the first author (2013). It is worth mentioning that we do not have a unified result, even though Bacher's result and ours are very similar.

Let L be an infinite regular language on a totally ordered alphabet (A, Comment: 10 pages, 3 figures

Blanchard and Fabre (1994) have considered description of symbolic systems by sequences obtained by iteration of two mappings gj and dj, defined by gj(u) = u[u]j and dj = u[u]Rj, where the word [u]j is obtained from a word u by removing the last j symbols. They stated a conjecture that the iteration of dj results in an automatic sequence. We prove here that dj is, while gj is not, a 2-automatic sequence. Our result is obtained by investigation of two wider classes of sequences.

We generalize the classical notion of ab-automatic sequence for a sequence indexed by the natural numbers. We replace the integers by a semiring and use a numeration system consisting of the powers of a baseb and an appropriate set of digits. For example, we define (−3)-automatic sequences (indexed by the ordinary integers or by the rational integers) and (−1 +i)-automatic sequences (indexed by the Gaussian integers). We show how these new notions are related to the old ones, and we study both the number-theoretic and automata-theoretic properties that permit the replacement of one numeration system by another.

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.

In this talk I will report on some recent results concerning decidability and enumeration for properties of automatic sequences. This is work with Jean-Paul Allouche, Emilie Charlier, Narad Rampersad, Dane Henshall, Luke Schaeffer, Eric Rowland, Daniel Goc, and Hamoon Mousavi.

Mix-automatic sequences form a proper extension of the class of automatic sequences, and arise from a generalization of finite state automata where the input alphabet is state-dependent. In this paper we compare the class of mix-automatic sequences with the class of morphic sequences. For every polynomial ϕ we construct a mix-automatic sequence whose subword complexity exceeds ϕ. This stands in contrast to automatic and morphic sequences which are known to have at most quadratic subword complexity. We then adapt the notion of k-kernels to obtain a characterization of mix-automatic sequences, and employ this notion to construct morphic sequences that are not mix-automatic.

The aim of this paper is to study the closure of the orbit of sequences obtained by iterating maps on words g ( u ) = u . u 1 , d ( u ) = u . 1 [ u °], and product g ∘ d , where u 1 is word u without its last letter, 1 u is word u without its first letter and u ° is its mirror image. It is shown that d thus generates a periodic orbit, g a subshift of finite type and g ∘ d an automatic sequence.

Proof. (1) We trivially have the bound f(n) ≤ n. On the other hand we have ν2(k) ≤ log k log 2 , and hence f(n) ≥ mink≥n k − log k log 2 . Since the derivative of the function t− log t log 2 is 1− 1 t log 2 , which is positive for t ≥ 2, for n ≥ 2 the minimum is attained for k = n and we conclude f(n) ≥ n− logn log 2 , and the first claim is proven. (2) We want to show that as k runds over all integers ≥n the minimum in (1) is attained at k = n or at k = 2 = n + 3 · 2. From this our claim follows by computing the value of k − ν2(k) at these two positions. Assume first that k ≥ n is not divisible by 2. Then we have k − ν2(k) ≥ n − ν2(k) ≥ n − m, which is what we want to have. Next assume that ν2(k) > m and k 2. For 2 2− (` + m + 2), and hence this range cannot contribute to the minimum. Finally, if k ≥ 2, then k−ν2(k) ≥ k− log k log 2 ≥ 2 −(`+m+3) > 2−(`+m+2), and this range is of no importance as well. Hence, the second claim follows as well.

We show that various aspects of k-automatic sequences -- such as having an unbordered factor of length n -- are both decidable and effectively enumerable. As a consequence it follows that many related sequences are either k-automatic or k-regular. These include many sequences previously studied in the literature, such as the recurrence function, the appearance function, and the repetitivity index. We also give a new characterization of the class of k-regular sequences. Many results extend to other sequences defined in terms of Pisot numeration systems.

In this paper, we introduce a notion of a right-sequential function on infinite words. The main result is that any rational function is the composition of a right-sequential function and a left-sequential function. This extends a classical result of Elgot and Mezei on finite words to infinite words. We also show that our class of right-sequential functions includes the normalization of real numbers in some base and the truth value of linear temporal logic. Finally, we apply the decomposition theorem to show that automatic sequences are preserved by rational letter-to-letter functions.

Given a morphism h prolongable on a and an integer p, we present an algorithm that calculates which letters occur infinitely often in congruent positions modulo p in the infinite word hω(a). As a corollary, we show that it is decidable whether a morphic word is ultimately p-periodic. Moreover, using our algorithm we can find the smallest similarity relation such that the morphic word is ultimately relationally p-periodic. The problem of deciding whether an automatic sequence is ultimately weakly R-periodic is also shown to be decidable.

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.

An infinite word is S-automatic if, for all n>=0, its (n + 1)st letter is the output of a deterministic automaton fed with the representation of n in the considered numeration system S. In this extended abstract, we consider an analogous definition in a multidimensional setting and present the connection to the shape-symmetric infinite words introduced by Arnaud Maes. More precisely, for d>=2, we state that a multidimensional infinite word x : N^d \to \Sigma over a finite alphabet \Sigma is S-automatic for some abstract numeration system S built on a regular language containing the empty word if and only if x is the image by a coding of a shape-symmetric infinite word.

We introduce the notion of aperiodicity measure for infinite symbolic sequences. Informally speaking, the aperiodicity measure of a sequence is the maximum number (between 0 and 1) such that this sequence differs from each of its non-identical shifts in at least fraction of symbols being this number. We give lower and upper bounds on the aperiodicity measure of a sequence over a fixed alphabet. We compute the aperiodicity measure for the Thue---Morse sequence and its natural generalization the Prouhet sequences, and also prove the aperiodicity measure of the Sturmian sequences to be 0. Finally, we construct an automatic sequence with the aperiodicity measure arbitrarily close to 1.

In some particular cases we give criteria for morphic sequences to be almost periodic (=uniformly recurrent). Namely, we deal with fixed points of non-erasing morphisms and with automatic sequences. In both cases a polynomial-time algorithm solving the problem is found. A result more or less supporting the conjecture of decidability of the general problem is given.

We propose a new ternary infinite (even full-infinite) square-free sequence. The sequence is defined both by an iterative method and by a direct definition. Both definitions are analogous to those of the Thue-Morse sequence. The direct definition is given by a deterministic finite automaton with output. In short, the sequence is automatic., Comment: 9 pages, 1 figures, to appear in Information Processing Letters

We introduce the notion of a k -synchronized sequence, where k is an integer larger than 1. Roughly speaking, a sequence of natural numbers is said to be k -synchronized if its graph is represented, in base k , by a right synchronized rational relation. This is an intermediate notion between k -automatic and k -regular sequences. Indeed, we show that the class of k -automatic sequences is equal to the class of bounded k -synchronized sequences and that the class of k -synchronized sequences is strictly contained in that of k -regular sequences. Moreover, we show that equality of factors in a k -synchronized sequence is represented, in base k , by a right synchronized rational relation. This result allows us to prove that the separator sequence of a k -synchronized sequence is a k -synchronized sequence, too. This generalizes a previous result of Garel, concerning k -regularity of the separator sequences of sequences generated by iterating a uniform circular morphism.

In the following pages we discuss infinite sequences defined on a finite alphabet, and more specially those which are generated by finite automata. We have divided our paper into seven parts which are more or less self-contained. Needless to say, we feel that the order we propose is the most natural one. References appear at the end of each one of the parts which implies some redundancy.

The automatic sequence is the central concept at the intersection of formal language theory and number theory. It was introduced by Cobham, and has been extensively studied by Christol, Kamae, Mendes France and Rauzy, and other writers. Since the range of an automatic sequence is finite, however, their descriptive power is severely limited.

Structural properties, local and asymptotic, of members of a class of simple, realtime generable sequences are analyzed.

Let A=(A(i,j))"i","j"="0^~ be a q-automatic double sequence over a finite set @W. Let [email protected][email protected] and assume that the number N"g(A,n) of g's in the nth row of A is finite for each n. We provide a formula for N"g(A,n) as a product of matrices according to the digits in the base q expansion of n. This formula generalizes several results on Pascal's triangle modulo a prime and on recurrence double sequences. It allows us to relate the asymptotic typical behavior of N"g(A,n) to a certain Lyapunov exponent. In some cases we determine this exponent exactly.

This paper deals with one-dimensional bidirectional sequences ā:Z→V, V a finite set, such that any p-decimation (|p|⩾2) of the sequence reproduces the sequence (modulo a certain shift). We develop a procedure for solving the underlying decimation-invariance (DI) equations and find that the number of solutions is always finite. Conditions for equivalency among solutions of differently parametrized DI-problems, and for possible periodicity and symmetry of solutions, are derived. It is shown that the set of all possible p-based decimations of a such a DI sequence (the so-called full kernel of the sequence) is finite. This implies finiteness of the kernel for the separate right and left parts of the sequence, and also |p|-automaticity of these parts. An algorithm is presented that constructs the kernel and associated |p|-automaton of a DI-sequence explicitly.