On p/q-recognisable sets
Victor Marsault
cs.LO cs.DM cs.FL
=1




17312
LastPage
Oct. 09, 2020Jul. 28, 2021















[figure]labelfont=bf







enuminlineenumerate*2
[enuminline]label=*),itemjoin*= and 

subthmenumerate3
[subthm]label=*,ref=*,
  
  font=,labelindent=*,leftmargin=*,start=1
  
  ,widest=a





vcsg/




































[1]⌊#1 ⌋
[1]⌈#1 ⌉





plain











claimClaim[thm]



 @hauteurcourrante
  @hauteursuivante
  @tempdim

proofwithbar[1][Proof of the claim]#1. 
falsetheoremXTheorem
falsetheorem[1]


















































































@xmd@d

@xmd@n

@xmd@s

@xmd@ss






[1]|#1|


















































































τ_pq












@@length





∈symbols"32


gather*
gather
equation
equation*
align
align*
multline
multline*




V. Marsault]Victor Marsault
LIGM, Université Gustave Eiffel, CNRS, F-77454 Marne-la-Vallée, France
Laboratory for Foundations of Computer Science, School of Informatics, University of Edinburgh, United Kingdom



victor.marsaultuniv-eiffel.fr
<http://victor.marsault.xyz>


On p/q-recognisable sets
    [
    
========================





  Let p/q be a rational number.
  
  Numeration in base  is defined by a function that evaluates each finite
  word over A_p={0, 1, …,p-1} to a rational number.
  
  We let  denote the image of this evaluation function.
  
  In particular,  contains all nonnegative integers and the literature on
  base  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 ()^d that are
  , realised by finite automata over ()^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 base numeration systems.
  
  Second, we show that the natural order relation and the modulo-q operator
  are not .  


On p/q-recognisable sets
    [
    
========================








§ INTRODUCTION




Let p and q be two coprime integers such that p>q>1, hence p/q
is an irreducible fraction greater than 1.

The base-p/q (numeration system) was introduced in <cit.>.

The study of such rational base numeration systems have enabled progress
to be made in solving deep problems from number theory (Josephus
and Mahler problems <cit.>).

Like other numerations systems, base p/q gives a way to
represent numbers by words, and to evaluate words to numbers.

Here, we consider only finite words over the canonical
alphabet =0,1,…,p-1; it is the smallest digit-set X
such that all nonnegative integers have representations using only digits
from X.



One paradox of base p/q is that simple number-sets are
represented by complicated languages and that simple languages are evaluated to
complicated number sets.

For instance,  is represented by a rather chaotic language, ,
that does not fit well in the usual hierarchy of formal languages.

On the other hand, the evaluations of all words over  form a set of
numbers, , which is hard to describe arithmetically.



Literature on base  mostly focuses on .

It is not a context-free language <cit.>
and even defeats any kind of iteration lemma <cit.>.

However, there is a very simple periodic procedure to generate  that is
similar to a breadth-first search <cit.>.

Some effort have also been made to study  from the perspective of
combinatorics on words
(frequency of patterns, sum-of-digit function, etc.
<cit.>).




On the contrary, there has been little work on .

Here, we start exploring this area by studying the subsets of  that are
realised by finite automata reading synchronously on d tapes.

We call such sets .

In the original article introducing base  <cit.>, it is shown
that addition is (in fact, normalisation of representations from any
finite alphabet).

This is a strong property which, in the case of integer base b leads to the
following characterisation of b-recognisable sets.



buch-bruy
  A subset of ^d is b-recognisable if and only if it is definable in the
  first-order logic ,+,V_b, where V_b is the function that maps n
  to the greatest power of b that divides n.  



Similar statements are also known for other numeration systems
(Pisot U-systems, Pisot β-numerations) and in other
settings (characterising the sets of infinite words realised by Büchi
automata) <cit.>.

In the present article, we show such a logic characterisation of sets,
stated below.



pq-defi<->pq-reco
  A subset of  is if and only if it is definable in the
  first-order logic 

    ,

  where
     is the function → that maps x to the greatest
    power of  that one may divide x by and obtain a quotient in .




It could seem strange that in our case, the universe is 
instead of .

However, since  is not a regular language,
the classical generalisation of Theorem 1 to rational base would clearly
not hold.

Note also that something is hidden in this statement.

In most numerations systems, natural order may be expressed using
addition (y≤ z may be expressed by ∃ x, x+y=z) and the
proofs of the logic characterisations (the one of buch-bruy)
rely on this fact.

On the contrary, this is not true in base  (see below) and we introduce
another pre-order relation (denoted by ) in our proof.






Very little is known about the expressive power of automata with respect to
base p/q.

In section <ref>, we begin to investigate this area.

First, we show that the natural order relation over  is not .

This is quite surprising since

  
  * the contrary is true in almost all numeration
systems, 
  
  * the natural order relation over  is recognised by a trivial finite
automaton, provided that we are ensured that input words belong to .




Second, we consider the modulo-n operator, where n is an integer constant.

This class of operators is related to the periodic subsets of  which,
since the work of Cobham, have a particular place within the study of
numeration systems.

In fact, most numeration systems S are such that 

  
  * 
is “S-recognisable”,
  
  * periodic subsets of  are S-recognisable.


(These properties hold if S belongs to the very large class of
regular abstract numeration systems <cit.>.)

In base p/q, neither Item 1 nor 2 hold;
it is not surprising since the relevant set of numbers is  rather
than .

By definition, the set  is , and the last part of this work is about
adapting Item 2.




If n is coprime with q, then the modulo-n operator is easy
to generalise as a function →/n and we show that it is 
(pqrec.modu).

On the other hand, when n is not coprime with q,
no generalisation of the modulo-n operator is obvious.

Nevertheless, we show that there is no set that separates q from
its complement in 
(npqrec.modu).

It follows that no generalisation of the modulo-n operator
would be if n is a multiple of q (npqrec.modu).







§ PRELIMINARIES





 §.§ Words, automata


An alphabet A is a finite set of symbols, called indifferently
letters or digits.

A word over A is a finite sequence u=a_k⋯ a_1a_0 of
letters from .

We let u denote the length of u, that is u=a_k⋯ a_1a_0=k.

For each i, 0≤ i≤u, we denote the prefix of u of length i
by i(u) that is i(u)=a_k… a_k-i;
similarly i(u)=a_i… a_0 denotes the suffix of u of
length i.

We denote the set of all words over A by A^* and
subsets of A^* are called languages over A.

The set A^* is endowed with the
concatenation, usually denoted implicitly as in u v,
or explicitly by a middle dot when it helps readability, as in u· v.




A (deterministic) automaton  is defined by a 5-tuple =⟨ A, 
Q_,  i_, δ_,F_⟩, where A is an alphabet, Q_ is
a finite set of states, i_∈ Q_ is the initial
state, δ_:Q_× A → Q_ is the (partial)
transition function and F_⊆ Q_ is a set of final
states.

As usual, we extend δ_ as a function Q_× A^*→
Q_ by δ_(q,ϵ)=q and δ_(q,a
u)=δ_(δ_(q,a),u).

We call the run of u, if it exists, the sequence of states
reached during the execution of  on u, namely, the finite
sequence (δ_(i_,i(u)))_0≤ i ≤u;
in particular, the phrase the run of u reaches state s
means that δ_ is defined on (i_,u) and
that δ_(i_,u)=s.

A word u is said to be accepted by  if its run exists and
reaches a final state; the accepted language of , denoted
by ()
is the set of the words accepted by .

An automaton is complete if its transition function is total.



It is sometimes more convenient to have an automaton read number
representations most significant digit first (MSDF), and sometimes
least significant digit first (LSDF).

Since the position of a digit is meaningful for evaluation, we try to keep
consistent the indexing of words throughout the article, hence we want to avoid
mirroring words and languages.

Thus, we say that an automaton is left-to-right if it reads its input in
a normal fashion, and right-to-left  if it reads
its input from right to left.

Since we usually represent numbers MSDF (Section <ref>),
left-to-right automata work on MSDF representations, while
right-to-left automata work on LSDF representations.

In a right-to-left automaton, the function δ_ is actually generalised
as δ_(q,u a)=δ_(δ_(q,a),u), and the run of a word u
refers to the state sequence
(δ_(i_,i(u)))_0≤ i≤u.


We will always consider automata in relation with a rational base numeration
system, hence automata will all be over the alphabet ()^d for some
number d of tapes.

(Rational bases and the digit set  are defined in defi-rati-base.)

A word u in  may be divided component-wise as u=(u_0,u_1,…,u_d)
where u_0,u_1,…,u_d are words in  that are of equal length.



The digit 0 always belongs to  and when d is clear from context,
we let 0 denote the letter (0,…,0) which is part of .

Moreover, we say that a d-tape automaton is padded if for every
word u in ,
u is accepted by  if and only if 0·u
is also accepted.

Intuitively, a padded automaton accepts words by value;
indeed, the i-th component of u and of 0·u
have the same value.

In the following, we will exclusively consider automata
that are padded.





 §.§ First-order logic


We briefly recall the definition of first-order formulas.

Let X be a countable set of variables.

Let Ω be a set called the domain,
let (f_i)_i∈ I be a family of functions,
let (R_j)_j∈ J be a family of relations on Ω,
and (c_k)_k∈ K be a family of constants in Ω.

We 
let

    Ω, (f_i)_i∈ I, (R_j)_j∈ J, (c_k)_k∈ K

denote the logic in which terms and formulas are
defined recursively as follows.

[label=•]
  
  * Each constant c_k, with k∈ K, and each variable x∈ X is a term.
  
  * If f_i is a n-ary function and t_0, …, t_n are terms,
        then f_i(t_0, …, t_n) is a term.
  
  * If t and t' are two terms, then t=t' is a formula.
  
  * If R_j is a n-ary relation and t_0, …, t_n are terms,
    then R_j(t_0, …, t_n) is a formula.
  
  * If ϕ is a formula, then ϕ is a formula.
  
  * If ϕ and ψ are formulas, then ϕψ, ϕψ and ϕψ are formulas.
  
  * If ϕ is a formula and x is a variable, then ∃ x ϕ and ∀ x ϕ are formulas


A variable x is called free in a formula ϕ if it appears outside
the scope of any quantifier ∃ x or ∀ x.

If a formula ϕ has d free variables, we usually make them explicit
by writing ϕ as ϕ(x_0,x_1,…,x_d).



We do not define in all generality the interpretation of relations, functions
and formulas since we will always use the straightforward interpretations.

Hence we assume that it is clear what it means for a closed formula
to be true and we say that a subset S of Ω^d is defined by the formula ϕ if the following holds.

    S=z∈Ω^dϕ( z) is true in Ω







 §.§ Rational base numeration systems

defi-rati-base









Let p and q be two coprime integers such that p>q>1; they will
be fixed throughout the article.

Note that p/q is thus an irreducible fraction greater than 1.

We define below base- (numeration system) ;
for more details see <cit.>.

Let us stress that it is not the special case of a
β-numeration where β is a rational number.




  §.§.§ Evaluation

The canonical alphabet associated with base , denoted by , is
the set =0,1,…,p.

The evaluation function  maps every word u=a_k-1⋯ a_1a_0
in  to a rational number as follows.

    eval(u)=(a_k-1⋯ a_1 a_0) =
      ∑^k-1_i=0a_i/q( )^i


The number (u) is called the value of u.

Note that the value of a word may be computed recursively: for every u,w∈,
the following holds.
eval-recu

    (u w)=   (u 0^w)+ (w) 
    
      =   (u)()^w + (w)






  We let  denote the image of the evaluation
  function: =().






The set  is hard to describe in another way than its definition, and in
general little is known about it.

Of course, eval implies that  contains only rational numbers
that have for denominator a power
of q.

Moreover, one may show that for a given power q^k, only
finitely many numbers in /q^k do not belong to  (see
<cit.> or vpq-ulti-all, later on).



  v32 gives an intuition of the content of  for
  base 3/2:
  the k-th line represent ∩/q^k and each
  number n/q^k in  is represented by a black segment of
  length 1/q^k centred around abscissa n/q^k;
  in each line, the highlighted segment always represents the number 5.
  
  The figure highlights the fact that as we refine the approximation of ,
  more and more holes appear in a seemingly chaotic fashion.












  §.§.§ Representation


Given a number x, we call expansion of x any word u in  such
that (u)=x.

By definition, each number in  has at least one expansion, and it is known
that it is unique up to leading 0's:


[<cit.>]repr-uniq
  If two words u and v in  are such that (u)=(v)
  and u≤v,
  then 0^i u= v for some nonnegative integer i.



We call representation of x and let (x) denote the unique
expansion that does not start by the digit 0.

Similarly, a d-tuple x=(x_0,…,x_d) in 
is represented by the unique word (x)=u=(u_0,…,u_d) in 
that does not start by 0 and
such that every u_i belongs to 0^*(x_i).




Every integer belongs to  and its representation may be computed by the following right-to-left
algorithm.
[An algorithm computing (x), for x in  and beyond, is given in <cit.>.]


MEA-alt
  
    MEA-alt-1(0) =   ϵ
    
        
    
        ∀ m∈, m>0  (m) =   (n) ·  a
        MEA-alt-2    where {[      n∈,  a∈; q m = p n +a ].






  We let  denote the set of the representations of nonnegative integers, that is =()

As briefly recalled in the introduction,  has been well studied; in the
present work we will use only the following two properties:  is prefix-closed
(follows from *MEA-alt) and it is not a regular language
(<cit.>).

Note that 0^* is also a prefix-closed language that is not regular.
















  §.§.§ sets


Let us now define for base  a notion analogous to the one
of b-recognisable sets defined in the context of an integer base b
<cit.>.



  Let d be a positive integer and S a subset of .
  
  
    
  * A d-tape automaton  is said to realise S
    if ()=(0)^*(S).
    
  * S is said  if it is realised by some automaton.
  



Note that item a implies in particular that  is padded and
that, since the expansions of a number are equal up to leading 0's, 
accepts by value: ()=^-1(S).



  
   is since ^()=,
  but  is not since ^()=0^* is not a regular language.
  






[<cit.>]addi
 Addition is .





Since it is central to our logic characterisation, we give without proof the
definition of _, the 3-tape right-to-left automaton that realises
addition in base .

addi

    _ = ⟨ [3], Q_, i_, δ_, F_ ⟩ ,

where the state set is Q_ = 0,…, m with m = 1+p-2/p-q;
the initial state is i_ = 0; the final-state set is F_=0; and
the transition function is defined as follows.
  
    ∀ s∈ Q_, ∀(a,b,c)∈[3]    δ_(s,(a,b,c)) = s'    if   q s+a+b = p s' + c




For instance, add_3_2 shows _ for base 3/2.



Note that δ_ is not a total function.

In fact, if s, a and b are fixed, there is exactly one c in  such
that δ_(s,(a,b,c)) is defined.

Hence, for each length i, there is exactly word u_i of length i
such that δ_𝒞(s,(0^i,0^i,u_i) is defined.
Moreover, if i≥ m, it may be shown 
that δ_𝒞(s,(0^i,0^i,u_i)=0.

In particular, the following holds.



   is stable by addition :  ∀ x,y ∈   x+y∈ .





  §.§.§ Different definition of rational bases



In this article, we use the original definition of rational bases <cit.>.
In <cit.>, the author define them
differently.  
Let us stress that the two definitions are not equivalent, although
they define two objects that are close.
Each has properties that the other has not, hence one object is
more convenient than the other depending on the context.

To make things precise, we give below the evaluation of a
word u=a_k-1⋯ a_0 in , as defined in <cit.>.

    (u)   =(a_k-1⋯ a_0) =
      ∑^k-1_i=0 a_i( )^i 
      
       = q (u)
 
With this definition, the (rather strange) factor 1/q
from eval does not appear.




The representation algorithm is modified as follows (the difference is
underlined).

  
    (0) =   ϵ
    
        
    
        ∀ m∈∖{0}  (m) =   (n) ·  a
        
              where {[       n∈,  a∈; q m = p n +qa ].


Finally, note that these changes propagate to other objects such as the one below.

    def=  = q⊊
    def=() = (1/q) = ·⊋


The main statements of this article (that is, pq-defi<->pq-reco,
npqrec.orde, *pqrec.peri, *insep,
and their corollaries) also hold, mutadis mutandis, for this alternative
notion of rational base numeration systems.







§ CHARACTERISATION OF SETS



The purpose of section  is to show our main result.

We restate it after a few definitions.




    
  * We let  denote the function →
      that maps 0 to 0, and every positive x to (p/q)^k,
      where k is the largest exponent such that x(p/q)^-k belongs to .
    
  * Let d be an integer and S be a subset of .
    
    We say that S is if it is defined by some formula in .
  




*pq-defi<->pq-reco
  A set is -recognisable if and only if it is p/q-definable.



The forward direction of pq-defi<->pq-reco
is shown in pq-reco->pq-defi (pq-reco->pq-defi) and
the backward direction in pq-defi->pq-reco
(pq-defi->pq-reco).
First, we show some preliminary results in length-preorder.















 §.§ Constants and the length preorder are 

length-preorder

vpq
  Let x be a number in  such that x≠0,
  and let i be a nonnegative integer.
  
  The following are equivalent.
  
    
  * There exists a letter a∈, a≠0, such that a0^i is a
    suffix of (x).
    
  * It holds (x) = ^i =(q 0^i).
  


  We denote the representation of x by (x)=u a 0^i
  with a≠ 0.
  
  From *eval-recu, it holds (u a)=x^-i; this
  number thus belongs to .
  
  On the other hand, if x^-(i) belonged in , it would be
  represented by some word w, and then w 0^i+1 would be an expansion
  of x, a contradiction to the uniqueness of representation
  (repr-uniq).
  
  Hence, (x)= ^i.
  
  The other direction is similar.



cons-pq-defi
  Every constant c in  is .


   First, let us show that there is a formula that realises 
   the natural order relation over (), that is over the image of
   , using the addition relation.
  cons-pq-defi:1
    Let x,y be two numbers in ().
    There exists z∈ such that x=y+z if and only if x≥ y.
  
  
      
  * The forward direction is immediate.
      
  * Backward direction. The case x=0 and the case y=0 are trivial.
    If x≠0 and y≠ 0 the representations of x and y are
    respectively written as (x)=q0^i and (y)=q0^j for some
    nonnegative integers i and j.
    Hypothesis implies that i≥ j and it may be verified 
    that z=((p-q)^i-j0^j) satifies x=y+z.
    
  

  
  The number 0 is the neutral element for addition, hence the set {0} is
  defined by the following formula.
  
    (x)   ∀ y   x+y=y

  cons-pq-defi:1 allows us to define the set {1} with
  the following formula.
  
    (x)   (x)= x ∀ y  ( (y)=y  ((y) ∃ z  x+z=y ))

  
  Then, for every other number z in , written as z=n/m,
  the set {z} is by the following formula.
  
    _z(x)    ∃ y  (y) [-.75ex]0pt1pty+y+⋯+y_n times  =[-.75ex]0pt1ptx+x+⋯+x_m times

  (Note that the formula _z
  is well formed for any z∈. However, if z does not belong to ,
  this formula defines the empty set.)


Since all constants are , in the following, we use in formulas, directly
numbers as terms.
For instance we will write  ϕ(x,y) x+p/q = y  instead
of  ϕ(x,y)∃ z _p/q(z) x+z = y.


    We denote the length preorder over  by  :
      for every x,y∈, we write x y  if  (x)≤(y).



The remainder of this subsection  is dedicated to showing
that relation  is definable in  (lord-pqrec).

The general idea is that 


  * the natural order is if it is restricted to the set of the numbers
whose representations use only the digit (p), 

  * the function that maps a number x∈ to (p)^(x) is
also .



  Let us define a formula a(x), for each letter a∈, a≠ 0.
  
  Equation (<ref>) defines the case a=(p-q) and
  Equation (<ref>) the other cases.

    p-q(x)   ∃ z  (z)=z  x + 1 = z
      
    a(x)    ∃ y  [-.75ex]0pt1ptx + x + ⋯ + x_p-q times = [-.75ex]0pt1pty + y + ⋯ + y_a times  ∧  p-q(y)


  

  For each a∈, a≠0, formula a(x) defines the
  set x∈(x)∈ a^*. 


    
  * Case a=p-q. 
    First, note that Equation (<ref>), below, is a direct consequence
    of how carry is propagated in base p/q.
    See the definition of the additionner (Equation (<ref>));
    and recall that the number 1 is represented by the one-letter word q in
    base p/q.
    
    ∀ x∈,  n∈ℕ  (x) = (p-q)^n (x+1) = q0^n


    
      
  * Forward direction. Let x be a number in  such that p-q(x) holds.
      Equation (<ref>) implies that the number z=x+1 is equal
      to (p/q)^i, for some nonnegative integer i, hence written
      (z)=q 0^i.
     From (<ref>), the number x'=((p-q)^i) is such that
     x'+1=z, hence x=x'. 
     Since p/q-representation is unique up to leading zeroes,  it holds (x)=(p-q)^i.

    
  * Backward direction is a direct consequence of (<ref>).
  
  
  * Case a≠ p-q (and a≠ 0).
      Let x be a number in  and n be a non-negative integer.
      The following equivalences conclude the proof.
      
    (x)= a^n 
             x = (a^n) 
            p-q/a x = ((p-q)^n) 
            
    (p-q/a x) = (p-q)^n

      (Note that in (<ref>), the equality already implies that y is necessarily equal to p-q/ax, if this number indeed belongs to .)


We now define a formula that enables to mask the actual value of a
number, but keeps the length of its representation.
Effectively, it replaces each digit by p (that is, by the greatest digit).
This is done in two steps: (x,z) is true if there is a word w
such that (w)=x and (w')=z, where w' is the word resulting
from replacing every digit in w by p; note that w may contain
leading 0's.
We say that z masks x if (x,z) is true.
Then, (x,y) is true if y is the smallest mask of x, that is, if it
is masked by every mask of x.
  
    (x,z) := p(z) ∃ y  x+y=z 
        
    (x,y) :=(x,y) ∀ z    (x,z) →(y,z)

Now, let us show that  has the intended behavior.


  Let x and y be two numbers in .
  
    
  * reduce
    It holds (x,z) if and only if (z) belongs to (p)^* and
    (z)≥(x).
    
  * norm
    It holds (x,y) if and only if it holds y=((p)^n), with n= (x).
  



  
  * We write u=(x) and n=u.
  
  
    
  * Forward direction.
    Obviously, (z) is equal to (p)^m for some m; it remains to show
    that m≥ n. 
    The definition of the additioner (Equation (<ref>))
    implies that no transition coming in state 0 outputs the digit 0, except
    the (0,0,0) loop.  
    
    In other words, the representation of a sum is never shorter than the
    representation of one of the operands.

    
  * Backward direction.
    Let m be the nonnegative integer such that (p)^m = (z),
    hence by hypothesis we have m≥ n.
    Let a_m⋯ a_1 a_0 = 0^m-n(x).  For each integer i, 0≤
    i<m, the number (p-1-a_i) belongs to {0,1,…,p}, hence is a
    digit in A_p.
    Hence, the word w=(p-1-a_m)⋯(p-1-a_1)(p-1-a_0)
    belongs to (A_p)^*
    and y=(w) belongs to .
    It is clear that x+y=z since no carry will be risen during this addition;
    hence y is the witness that (x,z) holds. 
  
  
  * From Item (a), any number with representation (p)^n may be
  reduced to any number with representation (p)^m if n≥ m.  
  
  The statement follows.


Now, all is set to show that relation  is . 

lord-pqrec
  The relation  is definable in .

 Let us show that the following formula defines .
  
    Φ(x,y) ∃ x' ∃ y'  (x,x') (y,y') (x',y')


  
    
  * Forward direction. Let x,y∈ be two numbers such that Φ(x,y) is true.
  From norm, the following two equations hold.
  
    x'= (p)^n  with n=(x)
    
        y'= (p)^m  with m=(y)

  From reduce,  since (x',y') is true, it holds n≤ m,
  hence x y.

    
  * Backward direction. Let x,y∈ be two numbers such that x y.
  We let n and m denote the length of the representation of x and y,
  respectively; hence n≤ m.
  The numbers x'=((p-1)^n) and y'=((p-1)^m) are the witnesses
  that Φ true.
  

 





 §.§ Every set is 

pq-reco->pq-defi

Section  is dedicated to the proof of
pq-reco->pq-defi.

It is adapted from the proof of buch-bruy given in <cit.>.

The main idea is to code the run of a d-state automaton, that is a sequence
of elements from {0,1,…,d}, by a d-tuple of 
numbers in [d].

The of the numbers in the d-tuple contain only 0's and 1's, and
are the characteristic functions of the respective state.

For instance, with d=4, the sequence
(s_0,s_1,s_2,s_3,s_4,s_5,s_6)=(3,0,3,1,1,1,1) is coded by the 4-tuple
(x_0,x_1,x_2,x_3)∈[4] defined by the following.

    ((x_0),(x_1),(x_2),(x_3))=(10,1111000,ϵ,101)

Indeed, the digit at position 0 in (x_3) is 1 because s_0=3; the
digit at position 1 in (x_0) is 1 because s_1=0, etc.





extr-pred, below, gives a few relations and functions that will
be useful in the proof and extr-pred shows that they are .

In particular, it gives the formula that computes the digit at a given position
in the representation of a given number.

First, let us clarify what we mean by position in a representation.

Let x be a number in , the representation of which we
write (x)=a_n-1⋯ a_1 a_0.

For every nonnegative integer i, the digit at position i
in (x) refers to a_i if i<n, and to 0 otherwise.


extr-pred
    
  * Let  be the function → that maps 0 to 0
      and every positive x to (1 0^i), where i is the
      integer such that (x)=u a 0^i, with a≠ 0.
    
  * We write (x) if x if the
          representation of x belongs to the language 1 0^*.
    
  * Similarly to x y, we write x< y if (x)<(y).


    
  * For each digit a∈,  we let ∗_a(y,z) denote the
    multiplication-by-a-digit relation: it
    holds ∗_a(y,z) and z=a× y.
    
  * For each digit a∈, let _a(x,y) be the relation that
    holds if (y) and if a is the digit at position i in (x),
    where i is the position of the unique digit 1 in (y).
  



extr-pred
  Functions and relations from extr-pred are all .


vmtmpvmtmp


@true@leqno

()
(x) = z     (x)=[-.75ex]0pt1exz+⋯+z_q times0pt

If x=0, the above formula is obviously correct.
Otherwise, from vpq, it holds (x)= ^i and z=1/q^i.

eval yields that z=(1 0^i).




    (x)      (x)=x  (x = 0) 
    
    
              x<y 
             
    
                x≤ y  (y≤ x) 
    
    
      ∗_a(y,z)         z =y+⋯+y_a times


It is a routine to show that the formula defined by b,
c and d are correct.


    _a(x,y) 
    (y)_i∃ℓ ∃ m ∃ r
        (
           x=ℓ+m+r^ii∗_a(y,m)^iii
    (ℓ=0  y<(ℓ))_iv r< y_v)

Assume that _a(x,y), as defined by e is true.
  
  Term i implies that there is an
  integer i such that (y)=10^i.
  
  The variable ℓ, m and r will contain the left, middle and right parts
  of x where the split is done at position i of the representation of x.
  
  Term iii ensures that (a 0^i)=m.
  Term iv ensures that
  there is a word u∈ such that (u 0^i+1)=ℓ.
  Term v ensures that (r)=v for some word v such that v≤ i.
  
  Then, ii implies that
  
    x=(u 0^i+1)+(a 0^i)+(v) = (u a 0^jv)
          where   j=i-v .

  
  Hence, the digit at position i in (x) is a.
  

  
  Conversely, let x be any number in  and y be a number in 
  such that y=1/q()^i for some integer i.
  
  For k great enough, we factorise 0^k(x) as u  a v  where u and v are two words in 
  such that v=i, and a is a letter in .
  
  The values ℓ=(u), m=(a 0^i)
  and r=(v) will be the witnesses that _a(x,y), as defined by
  e is true.
  



Now, let us show the forward direction of pq-defi<->pq-reco,
restated below.


pq-reco->pq-defi
  Every set is -definable.


  Let S be a subset of  that is , hence realised
  by a d-tape automaton .
  
  We let m denote the number of states in .
  
  Without loss of generality, we assume that  is right-to-left, complete,
  that the state-set is {0,1,…, m-1} and that the initial state is 0.
  
  We moreover denote by F the set of final states and by δ the
  transition function. 
  
  In summary, = ⟨, {0,1,…, m-1}, 0, δ, F
  ⟩ .
  

  

  
  Let x=(x_0,x_1,…,x_d) be a d-tuple of numbers.
  
  The formulas will describe the run of the word u=(x).
  
  
  First, we introduce a variable k equal to (1 0^K)
  where K is the length of u.
  
  Hence, K is equal to the max of the
  lengths (x_0), …,(x_d).
  
  Second, we introduce one variable per state of , denoted
  by s_0,s_1,…,s_m.
  
  The proof consists in proving that, for every integer n, 0≤ n ≤u,
  
    pq-defi<-pq-reco-pre∀ i, 0≤ i < m,
    the digit at position n in (s_i) is  {[                                  1 if the run of n(u) reaches state i;                                  0                          otherwise ]. 
    where n(u) is the suffix of u of length n.

  

  

  pq-defi<-pq-reco-L, below, gives the formula Λ() that defines k.
  
    pq-defi<-pq-reco-LΛ(x_0,x_1,…,x_d,k) 
    (k)(⋀_i=0^d-1  x_i< k )
        (∀ j   ((j)  j < k)
        ⋁_i=0^d-1j≤ x_i )


  
    The formula Λ(x_0,x_1,…,x_d,k) is true 
    if and only if
    k=1/q(p/q)^K,
    where K= {(x_i)}_0≤ i< d.
  
  
  It is a routine to establish the following equivalence.
  
    
  * The formula (k) is true if and only k=1/q(p/q)^K', where K'=((k)-1).
    
  * The formula ⋀_i=0^d-1  (x_i< k) is true
    if and only if it holds (k)>x_i, for each i, 0≤ i < d.
    
  * The formula

    (∀ j   ((j)  j < k)
      ⋁_i=0^d-1(j≤ x_i) )

    is true if and only if, for each J<K, there exists i such that (1/q(p/q)^J)≤(x_i).
  
  Claim  immediately follows.
  
  
  

  pq-defi<-pq-reco-I, below, defines ξ() expressing
  that 0 is the initial state.





  
  
    pq-defi<-pq-reco-Iξ(s_0,s_1,…,s_m)  _1(s_0,1/q) ⋀_i=1^m-1_0(s_i,1/q)


  
    The formula ξ(s_0,…,s_m)
  is true if and only if
      pq-defi<-pq-reco-pre holds for n=0.
  
  
  Recall that 1/q=(1).
  Hence ξ(s_0,s_1,…,s_m) is true if and only if both
  
    
  * the digit at position 0 in (s_0) is 1, and
    
  * for each i, 0<i<m, the digit at position 0 in (s_i) is 0.
  
  This concludes the proof of Claim  since 0 is the initial state.
  

  Provided that k is of the form k=1/q(p/q)^K, pq-defi<-pq-reco-F, below, defines Φ() which
  is true if the run of K(u) reaches a
  final state.
  
  (Recall that F is the set of final states.)
  
  
    pq-defi<-pq-reco-FΦ(s_0,s_1,…,s_m-1,k)   
    
          ⋁_i∈ F_1(s_i,k)

  
  The following claim immediately follows.
  
    The formula (Λ(x_0,x_1,…,x_d,k)Φ(s_0,s_1,…,s_m-1,k)) is true if and only if the following two conditions hold.
    
      
  * k=1/q(p/q)^K,
        where K= {(x_i)}_0≤ i< d
      
  * There exists an integer i∈ F, such that the digit at
        position K in s_i is 1.
    
  

  

  pq-defi<-pq-reco-D, below,  defines Δ() that will
  ensure that pq-defi<-pq-reco-pre is inductively satisfied.
  (Recall that δ is the transition function of ).  
    Δ(x_0,⋯,x_d, s_0,⋯,s_m,j) 
    ∃ h   0pt2exj+⋯+j^p times = 0pt2exh+⋯+h^q times                                
    ⋀_a = (a_0,⋯,a_d)∈
    0 ≤ i < m((_1(s_i,j) ⋀_ℓ=0^d-1_a_ℓ(x_ℓ,j)) 
    
    
    
    
        pq-defi<-pq-reco-D(_1(s_δ(i,a),h) ⋀_0 ≤ g < m 
    g ≠ δ(i,a)_0(s_g,h) ))

  
    Let J be a nonnegative integer. We assume that
    pq-defi<-pq-reco-pre holds for n=J, and we
    write j=1/q(p/q)^J.
    The formula Δ(x_0,⋯,x_d, s_0,⋯,s_m,j) is true
    if and only if pq-defi<-pq-reco-pre
    holds for n=(J+1).
  
  
    Since pq-defi<-pq-reco-pre holds for n=J,
    there is exactly one integer i in {0,…,m} such that
    _1(s_i,j) is true;
    and i is the state reached by the run of J(u), the suffix of
    length J of u.
    Moreover for each ℓ, 0≤ℓ<d, we let b_ℓ denote
    the digit such that _b_ℓ(x_ℓ,j) is true.
    Finally, we write i'=δ(i,(b_0,…,b_d)),
    or, in other words, i' is the state reached by the run
    of (J)(u).
    
    In this context, Δ(x_0,⋯,x_d, s_0,⋯,s_m,j) is
    equivalent to the following.
    
    ∃ h   [-.75ex]0pt0ptj+⋯+j_p times = [-.75ex]0pt0pth+⋯+h_q times(_1(s_i',h) ⋀_0 ≤ g < m 
    g ≠ i'_0(s_g,h) )

  The first conjunct is true if and only if h=(1 0^J+1),
  hence the whole formula is true if and only if both
    
      
  * the digit at position J+1 in (s_i' ) is 1; and
      
  * the digit at position J+1 in (s_g) is 0 if g≠ i'.
    
  This concludes the proof of Claim .
  

  

  
  Finally, pq-defi<-pq-reco-tota gives the
  formula Ω() of the logic  that defines the set S.
  
  We use x and s has shorthand for (x_0,x_1,…,x_d)
  and (s_0,s_1,…,s_m).

  
    pq-defi<-pq-reco-totaΩ(x_0,x_1,…,x_d) 
    ∃ k ∃s  Λ(x,k)
         ξ(s)
         Φ(s,k)
         ∀ j (  ((j)
         j < k ) Δ(x,s,j))

  It follows from the previous claims that Ω() defines the
  set S, concluding the proof of Proposition .






 §.§ Every set is 

pq-defi->pq-reco


The backward direction of pq-defi<->pq-reco is proved in a very
classical way.  We only give a sketch of the proof.

It amounts to showing that 1) each atomic set or relation of the logic is
realised by an automaton 2) the inductive constructs of first-order formulas
preserves .

For more details, see for instance <cit.>.



pq-defi->pq-reco
  Every p/q-definable set is -recognisable.


  Let  be a d-tape complete automaton
  that realises a d-free-variable formula Φ.




  

    
  * The set defined by the formula Φ(x) is realised by
    the automaton resulting from inverting final and non-final states in .
    
  * The set defined by the formula ∃ x_i  Φ(x) is
    realised by the automaton resulting from erasing the i-th tape
    from .  
    
    (Note that the resulting automaton needs to be determinised and made
    padded.)
    
  * The formula ∀ x_i  Φ(x) is equivalent to (
    ∃ x_i  Φ(x)).
    
  * Let S be the set of [d+1] defined
      by 
      
    Θ(x_0,x_1,…,x_i,y,x_i+1,…,x_d)   Φ(x)

      that is, where the "free" variable y is added without being used.
      
      S is realised by  defined as follows.
     is a d+1-tape automaton and it has the same state set, initial state and final-state set as .
    The transition function of  is defined by, for all appropriate a_i's, b and s,
      
    δ_(s,(a_0,… a_i,b,a_i+1,…,a_d)) = δ_(s,(a_0,…, a_d)) .

    
  * It is a routine to build the automaton that realises the set S defined by
      
    Π(x_0,…,x_i,x_k,x_i+1, …,x_k,x_i,x_k…,x_d)   Φ(x)

      that is, where the variables at positions i and k have swapped
      positions.

Let  be a second d-tape complete automaton that realises a
d-free-variable formulas Ψ. (Note that we may assume that Ψ
and Φ have the same free variables in the same order thanks to items
(d) and (e), above.)
  
[label=•]
    
  * The set defined by Φ(x) Ψ(x) is realised by the product automaton ×.
    
  * The formula Φ(x) Ψ(x) is equivalent to (Φ(x) Ψ(x))







  
  It remains to show that equality, addition, and the function 
  are all .
  
  Since, the -expansions of a number are equal up to leading 0's,
  equality is obviously .
  We previously recalled in addi
  the definition of the automaton that realises addition in base .
  
  The function  is realised by a simple automaton with two states,
  the definition of which is given as a prototype in wpq.
  























§ NOTABLE SETS THAT ARE OR ARE NOT 

nota


During the research leading to pq-defi<->pq-reco, it became apparent
that very little was known on the expressive power of automata with respect to
base .

After recalling a few known or obvious results, we show that the
natural order relation over  is not .

Then, we study generalisations of the modulo-n operator in
Sections *modu-pqrec and *modu-not-pqrec.

We show that it is if n is coprime with q, and that it is not if n is a multiple of q.

These results are not immediate consequences of pq-defi<->pq-reco,
although it is sometimes useful in the proofs.




 §.§ A few known results


 The following are -recognisable.
  
  
  * 
  Addition: (x,y,z)∈^3x+y=z.
  
  * 
  Partial subtraction: (x,y,z)∈^3x-y=z
  
  * 
  Multiplication by a constant: (y,z)∈^2r y=z, where r∈.
  
  * 
  Interval bounded by constants:  z∈r<z<s, where r and s belong to .
  



Item *pqrec.addi is given in defi-rati-base.

Item *pqrec.subt and
*pqrec.mult follows immediately from the fact that addition
is (addi).

Item *prec.inte follows from the fact that such an interval
contains a finite number of elements from .






 The following are not -recognisable.
  


    
  * 
      Any infinite subset of .
    
  *  Any finitely-generated additive submonoid of , of the
    form x_0 + ⋯+x_n, with x_0,…,x_n∈.
  






Item *npqrec.inte.subset is a consequence of the
fact that  possess the Finite Left Iteration Property, (for
instance <cit.>).

Item *npqrec.fini-gene is the main result of a
previous work of the author and Sakarovitch <cit.>.







 §.§ Natural order

orde-not-pqrec


The purpose of this section is to show that the order relation is not (npqrec.orde).

First, we state an elementary property of .




vpq-ulti-all
  For every integer k,
  there is a bound m_k such that n/q^k belongs
  to , for every integer n≥ m_k.


  The words 10^k-1 and 1 are evaluated to p^k/q^k
  and 1/q, respectively; hence, both numbers belong to .
  
  Since  is stable by addition, it 
  contains 1/q^k(p^ki+q^kj), for every nonnegative
  integers i and j.
  
  Since p and q are coprime, when j runs
  through {0,1,…,p^k-1}, then q^k-1j runs through all residue
  classes modulo p^k-1.
  It follows that we may choose m_k=(pq)^k.
  



The bound m_k given is the proof is far from tight; a better, and seemingly
tight, bound is given by <cit.>.

In the following, we will use vpq-ulti-all under a different form,
given below.


vpq-all-inte
  For all real numbers α and β, such that 0≤α<β,
  there exist two numbers x,y in 
  such that
  
    α < x - y < β .



  There exist two integers k and h such that α<h/q^k<β.
  
  Then, we set x=m_k+h/q^k and y=m_k/q^k, where m_k is the
  bound given by vpq-ulti-all.




npqrec.orde
  The set (x,y)∈^2x<y is not .


  Let L=(v,w)∈[2](v)<(w).
  
  The proof amounts to showing that L is not a regular language.
  
  For the sake of contradiction, we assume that L is accepted by a n-state
  automaton  that we assume left-to-right, complete and minimal.
  

  
  We write ℓ=(n).
  
  For every i, 0≤ i ≤ n, vpq-all-inte, applied
  to α=i()^-ℓ and β=(i+1)()^-ℓ,
  yields two numbers x,y in  and we write (v_i,w_i)=((y,x)).
  
  We have just defined n words in [2] such that

  
    order-i∀ i, 0≤ i≤ n,   
        i < ((w_i 0^ℓ)-(v_i 0^ℓ)) < i+1 .




  
  Let i and j be integers such that 0≤ i,j≤ n.
  
  We write u_j=(0^ℓ-k(j),0^ℓ),
  with k=(j).

  
  It follows that the two components of (v_i,w_i)·u_j
  are evaluated to
  ((v_i 0^ℓ)+j) and (w_i 0^ℓ), respectively.
  
  Hence, from *order-i, (v_i,w_i)·u_j belongs to L
  if and only if i≥ j.
  

  
  Let M=u_1,…,u_n.
  
  The next equation sums up the previous paragraph.
  


  
    ∀ i, 0≤ i≤ n,  ((v_i,w_i)^L) ∩ M  = u_1,…,u_i

  
  Thus, the languages (0ex2.25ex(v_i,w_i)^L)_0≤
  i≤ n are pairwise distinct,
  hence Q≥ n+1, where
  (Q={(v,w)^L | (v,w)∈[2]}).
  
  On the other hand, since  is minimal and complete, its state set is
  precisely Q, hence Q=n, a contradiction.





  


  

  


  





  

  


  


  



  

  



  

  


  

  






  







 §.§ Equivalence modulo n, where n is an integer coprime with q

modu-pqrec


The function x↦ (xn) classically maps integers to elements of /n.

If n is coprime with q, we may extend this function to →/n
as follows.

We let q^ denote the element of /n such that qq^n =
1.

Let x be a number in .

There exist integers m,k such that x=m/q^k, and
we set

    mod
      xn=(m/q^k) n=m (q^)^k n  .


It may be verified that this generalised modulo-n operator
still distributes over addition and multiplication.

It is then quite elementary to show that the computation of equivalence
classes modulo n is .



pqrec.peri
  Let n be an integer coprime with q, and let R⊆ Z/nZ be a set of
  remainders modulo n.
  
  Then, the set P_n,R= z∈(zn)∈ R is .
  


  
  Once again, q^ denotes the element of /n such that (qq^)
  is equivalent to 1 modulo n.
  
  Let  be the left-to-right automaton defined as follows.
  
    modu-n = ⟨ , /n, δ_,  0,  R  ⟩      where  δ_(s,a) = q^(s p + a) n

  Using Equation *eval-recu and *modu-n, one may show
  with an induction over the length of u that, for every word u in 
  the run of u in  exists and reaches the
  state ((u)n).
  




pqrec.modu
  Let n be an integer coprime with q.
  
  The following relation is .
  
    (x,y)∈[2]xn=yn y∈0,1,…,n-1



  For every r in /n, pqrec.peri yields that
  the set P_n,r is ,
  hence it follows from pq-defi<->pq-reco, that it
  is by a formula Ψ_r(x).
  
  The relation of the statement is definable by the following formula.
  
    Φ(x,y)     ⋁_i=0^n-1( y=i Ψ_i(x))

  
  pq-defi<->pq-reco concludes the proof.

























 §.§ Equivalence modulo q

modu-not-pqrec


Unlike in the previous case, it is not obvious to extend the modulo-q operator
to .

However, as far as is concerned, the question is irrelevant:
any such generalisation is not .

It is the npqrec.modu of the next statement.


npqrec.modu
Any subset S of  such that S∩ = q is not .

 
  For the sake of contradiction, we assume that there exists _0, an
  automaton realising a set S⊆ that satisfies S∩ = q.
  
  pq-defi<->pq-reco yields that there exists, for every integer i, 0≤ i < q,
  an automaton _i=⟨, Q_i, δ_i, i_i, F_i ⟩ that realises S+i.
  
  Note in particular that the _i's are correct if the input is the expansion of an integer:
  
    ai-corr-inte∀ i, 0≤ i < q,  ∀ u∈, (u)∈,
    _i accepts  u  i=(u) q .




  
  We assume without loss of generality that the _i's are
  complete and left-to-right.
  


  Let  be the left-to-right automaton:
  
    = ⟨ , Q_, δ_, i_,  F_ ⟩

  where the state-set is Q_= Q_0×⋯× Q_q, the initial state is i_=(i_0,…,i_q),
  all states are final: F_=Q_, and δ_ is defined as follows.
  
  Let s=(s_0,s_1,…,s_q) be a state in Q_ and let a be a letter in .
  
    importantδ_(s,a)  is defined if and only if   s_i∈ F_i , 
    where i is the integer such that   i p+a ≡ 0 [q]



In this case, δ_(s,a)=(
      δ_i(s_0,a),  δ_i(s_1,a), …, δ_i(s_q-1,a)).



















  

  
  The important part of the definition of  is important;
  it should be compared with MEA-alt (which gives the algorithm
  to compute the representation of integers).
  
  Intuitively, important ensures that taking a transition in 
  preserves the property of being evaluated to an integer; it will yield
  bc-corr thanks to a proof by induction.
  
  The rest of the definition of  is simply such that bc-comp holds.
  

  bc-comp
    Let u be a word in .
    
    If the run of u in  exists and reaches the
    state (s_0,s_1,…,s_q), then for every i, 0≤ i < q, the
    run of u in _i exists and reaches s_i.
    
  
  
  From its definition, the automaton  is the result of two transformation
  applied to the classical automaton product _0×_1 ×⋯×_q:
  deleting some transitions and setting all states as final. Since the A_i's are all complete,
  Claim  follows.
  




  bc-corr
    A word u has a run in 
    if and only if (u) is an integer.
  
   By induction over the length of u; the case u=ϵ is trivial.

  Let u=v a be a non-empty word in .  Induction hypothesis then rewrites as
  
  bc-corr-i
  
    bc-corr-il
        v has a run in 
    ⇕
    bc-corr-ir(v) belongs to

  
  
  
  
  

  
  Note that u has a run in  implies *bc-corr-il, since v is a prefix of u;
  and that (v a)∈ implies *bc-corr-ir, since 0^* is a prefix-closed language.
  
  Hence, in both directions of the proof, both sides of the equivalence of *bc-corr-i hold.
  

  
  Then, we let s=(s_0,s_1,⋯,s_q) denote the state reached by
  the run of v in .
  
  Hence, for every integer i, 0≤ i < q, the run of v in _i 
  reaches s_i (bc-comp).
  
  From *ai-corr-inte, since (v) is an integer, v is accepted by _k, where k=(v)q,
  and rejected by each _i such that i≠ k.


  
  In other words, s_k∈ F_k and for every i≠ k, s_i∉ F_i.
  
  Then, the following are equivalent.

  

  u has a run in 
  
    
  * δ(s,a)=t for some t∈ Q_
    
  * s_i∈ F_i  and  i p + a≡ 0 [q]   (from *important)
    
  * k p + a ≡ 0  [q]  (since necessarily, k=i)
    
  * (v) p+a ≡ 0  [q]  (from the definition of k)
    
  * 1/q((v) p+a)∈
    
  * (v a)=(u)∈  (from *eval-recu)
  

  

  This concludes the proof of Claim .


  

  Since all states in  are final, bc-corr yields that the language accepted by  is 0^*,
  a contradiction.






The inseparability result stated  by npqrec.modu may be
generalised to every periodic set whose smallest period is a multiple of q.



insep
  Let P be a periodic set of integers, the smallest period of which is a
  multiple of q.
  
  Then, there is no set S such that S∩=P.


  Since bounded intervals are (prec.inte),
  we may assume that P is purely periodic.
  
  First, we assume moreover that the smallest period of P is exactly q.
  
  In this case, there exists a remainder set R⊆/q
  such that S=R+q.
  
  Using that q is the smallest period of P, simple arithmetics shows that the following claim holds.
  

  div
    An integer i is divisible by q if and only if,
    for every r in R, (i+r)q belongs to R
  


  For the sake of contradiction, we assume that there exists a set S
  as in the statement.
  
  We denote the formula that defines S by Φ(x).
  
  
  
  Let ξ(x) ⋀_r∈ RΦ(x+r)
  and let X be the set definable by ξ.
  
  div yields that ∩ X =q,
  
  From pq-defi<->pq-reco, X is , a contradiction
  to npqrec.modu.
  

  

  
  If the period of P is k q, k>1, a similar ab absurdo
  reasoning yields a set X such that ∩ X =k q.
  
  Then, using pq-defi<->pq-reco, it is easy to show that the set
  Y=X ∪ (X+q) ∪⋯∪ (X+(k-1) q) is also and
  satisfies Y∩ = q, a contradiction to npqrec.modu.
  



npqrec.modu
  Let k be a positive integer.
  Let f be a function → such that, for every integer n, f(n)=nk q.
  
  The function f is not .
  




In Sections *modu-pqrec
and *modu-not-pqrec, we studied the of the modulo-n
operator when n is coprime with q (pqrec.modu) and when n is
a multiple of q (npqrec.modu).

These results do not cover all cases, and in general we conjecture the
following.



  Let n be an integer.
  
  Let f be a function →.
  
  We assume that, for every number x/y in  such that y is
  coprime with n, then f(x/y)= (x y^-1)n,
  where y^-1 is the inverse of y in /n.
  

  
  Then, the function f is if and only if n is coprime with q.








§ CONCLUSION AND FUTURE WORK



In this work, we took a perspective which is classical for other numeration
systems (integer base, U-systems), but quite new in the studies on rational base
numeration systems.

Instead of exploring the intricacies of the language ,
we indeed started to determine what may or may not be computed by automata.

It is very encouraging that the logic characterisation given by
pq-defi<->pq-reco is similar to the corresponding statements
in other settings <cit.>.



This opens for base  a lot of questions that have been answered for others
numerations systems.

For instance, it is natural to confront to sets definable in Presburger
arithmetic.

Indeed Cobham Theorem and its generalisations <cit.> showed that a
set realised by automata in “sufficiently different” numerations systems is
necessarily definable in that logic.

In the case of base , the notion needs some adaptation, and
nota merely starts the research in that direction.





Another research direction would be to consider the fact that every real number
is represented in base 
by an infinite word over .

Then, one could study the subsets of ^d that are realised by d-tape
Büchi automata and establish whether there is a logic characterisation of
them, much like what is done in <cit.> for integer bases.

The considerable advantage would then be that the domain is always ,
independently of the base  considered.

Comparing to r/s-recognisability could then lead to a statement in
the spirit of Cobham Theorem, similar to the result in <cit.>.






§ ACKNOWLEDGEMENTS

  Some of the results in this article are part of the Ph.D thesis of the author
  <cit.>, written under the supervision of Jacques Sakarovitch.
  The author warmly thanks Arnaud Carayol for several helpful discussions that
  made the logic characterisation in pq-defi<->pq-reco more elegant.
  The author is also grateful to the reviewers for their many valuable
  comments, which greatly improved the presentation of the results.

BertRigo10-b,BertRigo18-b
alpha


