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-recognisables, 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\"uchi-Bruy\`ere Theorem for integer bases numeration systems. Second, we show that the natural order relation and the modulo-q operator are not p/q-recognisable.
翻译：Let p/ q 是一个理性的数值。 在 base p/ q 中的数值是由一个函数定义的, 该函数将A_ p ⁇ 0, 1,..., p-1} 上的每个限定单词评价为某种合理的数值。 我们让 N_ p/ q 表示此评价功能的图像。 特别是, N_ p/ q 包含所有非负整数, 基p/ q 上的文献通常侧重于被评价为非负整数的一组单词; 它是一个相当混乱的语言, 不是没有上下文的。 相反, 我们在这里研究的是( N_ p/ q) d 的子集, 它们是 p/ q- recogniversables, 即由 A_ p/ d。 首先, 我们给这些组设定了在第一顺序逻辑中可以解定义的特性, 类似于 B\ " uchi- Bruy ⁇ ere Theorem 提供的整数计算系统 。 其次, 我们显示自然秩序关系和modulo- q 经营人并非 p/ q- recognable.
相关内容
微信扫码咨询专知VIP会员