BZPEERPapers, people, evidence and research pathsDiscover
Research tools
Network
Opportunities
Account
Source author record
Victor Marsault appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
Catalog footprint
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
We present here the notion of breadth-first signature and its relationship with numeration system theory. It is the serialisation into an infinite word of an ordered infinite tree of finite degree. We study which class of languages corresponds to which class of words and,more specifically, using a known construction from numeration system theory, we prove that the signature of rational languages are substitutive sequences.
This work builds on the notion of breadth-first signature of infinite trees and (prefix-closed) languages introduced by the authors in a previous work. We focus here on periodic signatures, a case coming from the study of rational base numeration systems; the language of integer representations in base~$\frac{p}{q}$ has a purely periodic signature whose period is derived from the Christoffel word of slope~$\frac{p}{q}$. Conversely, we characterise languages whose signature are purely periodic as representations of integers in such number systems with non-canonical alphabets of digits.
This work is a contribution to the study of set of the representations of integers in a rational base number system. This prefix-closed subset of the free monoid is naturally represented as a highly non regular tree whose nodes are the integers and whose subtrees are all distinct. With every node of that tree is then associated a minimal infinite word. The main result is that a sequential transducer which computes for all n the minimal word associated with n+1 from the one associated with n, has essentially the same underlying graph as the tree itself. These infinite words are then interpreted as representations of real numbers; the difference between the numbers represented by these two consecutive minimal words is the called the span of a node of the tree. The preceding construction allows to characterise the topological closure of the set of spans.
In this work, it is proved that a set of numbers closed under addition and whose representations in a rational base numeration system is a rational language is not a finitely generated additive monoid. A key to the proof is the definition of a strong combinatorial property on languages : the bounded left iteration property. It is both an unnatural property in usual formal language theory (as it contradicts any kind of pumping lemma) and an ideal fit to the languages defined through rational base number systems.
It is decidable if a set of numbers, whose representation in a base b is a regular language, is ultimately periodic. This was established by Honkala in 1986. We give here a structural description of minimal automata that accept an ultimately periodic set of numbers. We then show that it can verified in linear time if a given minimal automaton meets this description. This thus yields a O(n log(n)) procedure for deciding whether a general deterministic automaton accepts an ultimately periodic set of numbers.