Search

The notion of $b$-regular sequences was generalized to abstract numeration systems by Maes and Rigo in 2002. Their definition is based on a notion of $\mathcal{S}$-kernel that extends that of $b$-kernel. However, this definition does not allow us to generalize all of the many characterizations of $b$-regular sequences. In this paper, we present an alternative definition of $\mathcal{S}$-kernel, and hence an alternative definition of $\mathcal{S}$-regular sequences, which enables us to use recognizable formal series in order to generalize most (if not all) known characterizations of $b$-regular sequences to abstract numeration systems. We then give two characterizations of $\mathcal{S}$-automatic sequences as particular $\mathcal{S}$-regular sequences. Next, we present a general method to obtain various families of $\mathcal{S}$-regular sequences by enumerating $\mathcal{S}$-recognizable properties of $\mathcal{S}$-automatic sequences. As an example of the many possible applications of this method, we show that, provided that addition is $\mathcal{S}$-recognizable, the factor complexity of an $\mathcal{S}$-automatic sequence defines an $\mathcal{S}$-regular sequence. In the last part of the paper, we study $\mathcal{S}$-synchronized sequences. Along the way, we prove that the formal series obtained as the composition of a synchronized relation and a recognizable series is recognizable. As a consequence, the composition of an $\mathcal{S}$-synchronized sequence and a $\mathcal{S}$-regular sequence is shown to be $\mathcal{S}$-regular. All our results are presented in an arbitrary dimension $d$ and for an arbitrary semiring $\mathbb{K}$., Comment: 38 pages, 13 figures

The aim of this short note is to generalise the result of Rampersad--Shallit saying that an automatic sequence and a Sturmian sequence cannot have arbitrarily long common factors. We show that the same result holds if a Sturmian sequence is replaced by an arbitrary sequence whose terms are given by a generalised polynomial (i.e., an expression involving algebraic operations and the floor function) that is not periodic except for a set of density zero., Comment: 6 pages

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

As a generalization of the sum of digits function and other digital sequences, sequences defined as the sum of the output of a transducer are asymptotically analyzed. The input of the transducer is a random integer in $[0, N)$. Analogues in higher dimensions are also considered. Sequences defined by a certain class of recursions can be written in this framework.Depending on properties of the transducer, the main term, the periodic fluctuation and an error term of the expected value and the variance of this sequence are established. The periodic fluctuation of the expected value is Hölder continuous and, in many cases, nowhere differentiable. A general formula for the Fourier coefficients of this periodic function is derived. Furthermore, it turns out that the sequence is asymptotically normally distributed for many transducers. As an example, the abelian complexity function of the paperfolding sequence is analyzed. This sequence has recently been studied by Madill and Rampersad.

In the paper, we give the recurrent equations of the Hankel determinants of the Cantor sequence, and show that the Hankel determinants as a double sequence is 3-automatic. With the help of the Hankel determinants, we prove that the irrationality exponent of the Cantor number, i.e. the transcendental number with Cantor sequence as its b-ary expansion, equals 2., Comment: 20 pages, 1 figure

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 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 reprove a few results concerning paperfolding sequences using properties of Catalan numbers modulo 2.