2022/02/08 by Émilie Charlier, Célia Cisternino, Charlier, Émilie +5 · 1 citation
Computer Science · #11K16 #11R06 #37B10 #68Q45 #Combinatorics (math.CO) #Computability, Logic, AI Algorithms #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Logic, programming, and type systems #Number Theory (math.NT) #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2202.03718
openalex publication_date 2022/02/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The first aim of this article is to give information about the algebraic properties of alternate bases \boldsymbolβ=(β0,…,βp-1) determining sofic systems. We show that a necessary condition is that the product δ=∏i=0p-1βi is an algebraic integer and all of the bases β0,…,βp-1 belong to the algebraic field \mathbb Q(δ). On the other hand, we also give a sufficient condition: if δ is a Pisot number and β0,…,βp-1∈ \mathbb Q(δ), then the system associated with the alternate base \boldsymbolβ=(β0,…,βp-1) is sofic. The second aim of this paper is to provide an analogy of Frougny's result concerning normalization of real bases representations. We show that given an alternate base \boldsymbolβ=(β0,…,βp-1) such that δ is a Pisot number and β0,…,βp-1∈ \mathbb Q(δ), the normalization function is computable by a finite Büchi automaton, and furthermore, we effectively construct such an automaton. An important tool in our study is the spectrum of numeration systems associated with alternate bases. The spectrum of a real number δ>1 and an alphabet A⊂ \mathbb Z was introduced by Erdős et al. For our purposes, we use a generalized concept with δ∈\mathbb C and A⊂\mathbb C and study its topological properties.