Victor Marsault - On p/q-recognisable sets

lmcs:6834 - Logical Methods in Computer Science, July 28, 2021, Volume 17, Issue 3 - https://doi.org/10.46298/lmcs-17(3:12)2021
On p/q-recognisable setsArticle

Authors: Victor Marsault ORCID

    Let p/q be a rational number. Numeration in base p/q is defined by a function that evaluates each finite word over A_p={0,1,...,p-1} to some rational number. We let N_p/q denote the image of this evaluation function. In particular, N_p/q contains all nonnegative integers and the literature on base p/q usually focuses on the set of words that are evaluated to nonnegative integers; it is a rather chaotic language which is not context-free. On the contrary, we study here the subsets of (N_p/q)^d that are p/q-recognisable, i.e. realised by finite automata over (A_p)^d. First, we give a characterisation of these sets as those definable in a first-order logic, similar to the one given by the Büchi-Bruyère Theorem for integer bases numeration systems. Second, we show that the natural order relation and the modulo-q operator are not p/q-recognisable.


    Volume: Volume 17, Issue 3
    Published on: July 28, 2021
    Accepted on: July 2, 2021
    Submitted on: October 9, 2020
    Keywords: Computer Science - Logic in Computer Science,Computer Science - Discrete Mathematics,Computer Science - Formal Languages and Automata Theory

    Consultation statistics

    This page has been seen 1256 times.
    This article's PDF has been downloaded 223 times.