Regular sequences and synchronized sequences in abstract numeration systems

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 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 S-kernel, and hence an alternative definition of 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 S-automatic sequences as particular S-regular sequences. Next, we present a general method to obtain various families of S-regular sequences by enumerating S-recognizable properties of S-automatic sequences. As an example of the many possible applications of this method, we show that, provided that addition is S-recognizable, the factor complexity of an S-automatic sequence defines an S-regular sequence. In the last part of the paper, we study 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 S-synchronized sequence and a S-regular sequence is shown to be S-regular. All our results are presented in an arbitrary dimension d and for an arbitrary semiring K.