paperbot · PL 论文追踪

全部论文 待读 收藏

P2 On p/q-recognisable sets

论 p/q-可识别集合
LMCS vol.Volume 17, Issue 32021匹配度 0/10 · 该论文研究有理数基 p/q 下的可识别集合、一阶逻辑刻画与自动机理论,属于纯逻辑/自动机/数论方向,与用户关注的程序静态分析、LLM/Agent、浮点程序分析、贝叶斯程序分析等方向没有直接关联。引用 0 inbox
Victor Marsault
crossref: 2026-09-10

AI 速览

一句话:研究有理数基 p/q 的可识别集合:给出一阶逻辑刻画,并证明自然序与模 q 运算不可识别。

设 p/q 为有理数,基 p/q 的计数系统用求值函数将 A_p={0,1,...,p-1} 上的有限词映射为有理数,其像记为 N_{p/q}。既有文献多关注求值为非负整数的词集,该语言相当混乱且非上下文无关。本文转而研究 (N_{p/q})^d 中由 (A_p)^d 上的有限自动机实现的 p/q-可识别子集。作者首先给出这类集合的一阶逻辑可定义性刻画,类似整数基计数系统中的 Büchi-Bruyère 定理;随后证明自然序关系与模 q 算子都不是 p/q-可识别的。

问题
如何刻画有理数基 p/q 下由有限自动机识别的集合,并判断自然序、模 q 等基本关系或运算是否可识别。
方法
在 p/q 计数系统上定义 p/q-recognisable 集合,将其与一阶逻辑可定义性建立对应,并用自动机与逻辑方法证明不可识别性。
评估
通过数学定理证明:给出类似 Büchi-Bruyère 定理的一阶逻辑刻画,并证明自然序关系与模 q 算子不可 p/q-识别。
原文摘要(Abstract)

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\"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.

链接与引用

DOI 原文 · PDF(开放获取) ·

BibTeX
@article{paperbot1292,
  title = {On p/q-recognisable sets},
  author = {Victor Marsault},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 17, Issue 3},
  year = {2021},
  doi = {10.46298/lmcs-17(3:12)2021}
}