A fundamental question in logic and verification is the following: for which unary predicates P_1, …, P_k is the monadic second-order theory of ⟨ℕ;<,P_1,…,P_k⟩ decidable? Equivalently, for which infinite words α can we decide whether a given Büchi automaton 𝒜 accepts α? Carton and Thomas showed decidability in the case that α is a fixed point of a letter-to-word substitution σ, i.e., σ(α) = α. However, abundantly more words, e.g., Sturmian words, are characterised by a broader notion of self-similarity that involves a set S of substitutions. A word α is said to be directed by a sequence s = (σ_n)_{n ∈ ℕ} over S if there is a sequence of words (α_n)_{n ∈ ℕ} such that α₀ = α and α_n = σ_n(α_{n+1}) for all n; such α are called S-adic. We study the automaton acceptance problem for such words and prove, among others, the following: given finite S and an automaton 𝒜, we can compute an automaton ℬ that accepts s ∈ S^ω if and only if s directs a word α accepted by 𝒜. Thus we can algorithmically answer questions of the form "Which S-adic words are accepted by a given automaton 𝒜?"

We study density of rational languages under shift invariant probability measures on spaces of two-sided infinite words, which generalizes the classical notion of density studied in formal languages and automata theory. The density for a language is defined as the limit in average (if it exists) of the probability that a word of a given length belongs to the language. We establish the existence of densities for all rational languages under all shift invariant measures. We also give explicit formulas under certain conditions, in particular when the language is aperiodic. Our approach combines tools and ideas from semigroup theory and ergodic theory.

For which unary predicates P 1 , … , P m is the MSO theory of the structure 〈 N ; < , P 1 , … , P m 〉 decidable? We survey the state of the art, leading us to investigate combinatorial properties of almost-periodic, morphic, and toric words. In doing so, we show that if each P i can be generated by a toric dynamical system of a certain kind, then the attendant MSO theory is decidable. We give various applications of toric words, including the recent result of [1] that the MSO theory of 〈 N ; < , { 2 n : n ∈ N } , { 3 n : n ∈ N } 〉 is decidable.

We investigate the decidability of the monadic second-order (MSO) theory of the structure (N; <, P1,…,Pk), for various unary predicates P1,…,Pk ⊆ N. We focus in particular on 'arithmetic' predicates arising in the study of linear recurrence sequences, such as fixed-base powers Powk = {kn : n ∈ N}, k-th powers Nk = {nk : n ∈ N}, and the set of terms of the Fibonacci sequence Fib = {0, 1, 2, 3, 5, 8, 13,…} (and similarly for other linear recurrence sequences having a single, non-repeated, dominant characteristic root). We obtain several new unconditional and conditional decidability results, a select sample of which are the following:

This article is devoted to the study of two arithmetical sources associated with classical partitions, that are both defined through the mediant of two fractions. The Stern-Brocot source is associated with the sequence of all the mediants, while the Sturm source only keeps mediants whose denominator is "not too large". Even though these sources are both of zero Shannon entropy, with very similar Renyi entropies, their probabilistic features yet appear to be quite different. We then study how they influence the behaviour of tries built on words they emit, and we notably focus on the trie depth. The paper deals with Analytic Combinatorics methods, and Dirichlet generating functions, that are usually used and studied in the case of good sources with positive entropy. To the best of our knowledge, the present study is the first one where these powerful methods are applied to a zero-entropy context. In our context, the generating function associated with each source is explicit and related to classical functions in Number Theory, as the ζ function, the double ζ function or the transfer operator associated with the Gauss map. We obtain precise asymptotic estimates for the mean value of the trie depth that prove moreover to be quite different for each source. Then, these sources provide explicit and natural instances which lead to two unusual and different trie behaviours.

We introduce and study a multiple gcd algorithm that is a natural extension of the usual Euclid algorithm, and coincides with it for two entries; it performs Euclidean divisions, between the largest entry and the second largest entry, and then re-orderings. This is the discrete version of a multidimensional continued fraction algorithm due to Brun. We perform the average-case analysis of this algorithm, and prove that the mean number of steps is linear with respect to the size of the entry. The method relies on dynamical analysis, and is based on the study of the underlying Brun dynamical system. The dominant constant of the analysis is related to the entropy of the system. We also compare this algorithm to another extension of the Euclid algorithm, proposed by Knuth, and already analyzed by the authors.

This paper provides a probabilistic analysis of an algorithm which computes the gcd of ℓ inputs (with ℓ ≥ 2), with a succession of ℓ - 1 phases, each of them being the Euclid algorithm on two entries. This algorithm is both basic and natural, and two kinds of inputs are studied: polynomials over the finite field Fq and integers. The analysis exhibits the precise probabilistic behaviour of the main parameters, namely the number of iterations in each phase and the evolution of the length of the current gcd along the execution. We first provide an average-case analysis. Then we make it even more precise by a distributional analysis. Our results rigorously exhibit two phenomena: (i) there is a strong difference between the first phase, where most of the computations are done and the remaining phases; (ii) there is a strong similarity between the polynomial and integer cases, as can be expected.