paperbot · PL 论文追踪

全部论文 待读 收藏

P2 ℤ-polyregular functions

ℤ-多正则函数
LICS 2023 38th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)2023匹配度 1/10 · 该论文属于纯形式语言与自动机理论,研究有限词到整数的ℤ-多正则函数及其逻辑、级数、转换器刻画,与用户关注的静态分析、LLM/Agent、浮点程序分析、贝叶斯程序分析等方向几乎没有直接交集。虽然形式化方法背景与形式验证有间接联系,但论文未涉及程序分析、LLM 或工业落地,因此匹配度很低。引用 0 inbox
Thomas Colcombet, Gaëtan Douéneau-Tabot, Aliaume Lopez
crossref: 2026-09-12dblp: 2026-09-12

AI 速览

一句话:研究从有限词到整数的ℤ-多正则函数,给出逻辑、表达式、级数与转换器刻画,并判定其子类成员问题。

本文研究从有限词到整数的稳健函数类——ℤ-多正则函数。作者分别用逻辑、ℤ-有理表达式、ℤ-有理级数和转换器给出自然刻画,从而统一了多种描述机制。随后考察两个子类成员判定问题:证明函数的渐近增长率可计算,且该增长率对应逻辑公式表示所需的最少变量数;并证明ℤ-多正则函数的一阶可定义性可判定。为得到后者,论文引入残差转换器这一新概念,并基于非周期性给出语义刻画。

问题
论文关注从有限词到整数的ℤ-多正则函数类,试图建立其多种等价描述,并解决其子类(如渐近增长率和一阶可定义性)的成员判定问题。
方法
通过逻辑、ℤ-有理表达式、ℤ-有理级数与转换器的等价刻画,并结合新引入的残差转换器和非周期性语义分析来研究函数的结构与可定义性。
评估
理论证明:给出渐近增长率的可计算性及其与逻辑表示最少变量数的对应,并证明一阶可定义性可判定。
原文摘要(Abstract)

This paper studies a robust class of functions from finite words to integers that we call ℤ-polyregular functions. We show that it admits natural characterizations in terms of logics, ℤ-rational expressions, ℤ-rational series and transducers.We then study two subclass membership problems. First, we show that the asymptotic growth rate of a function is computable, and corresponds to the minimal number of variables required to represent it using logical formulas. Second, we show that first-order definability of ℤ-polyregular functions is decidable. To show the latter, we introduce an original notion of residual transducer, and provide a semantic characterization based on aperiodicity.

链接与引用

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

BibTeX
@inproceedings{ColcombetDL23,
  title = {ℤ-polyregular functions},
  author = {Thomas Colcombet and Gaëtan Douéneau-Tabot and Aliaume Lopez},
  booktitle = {LICS},
  year = {2023},
  doi = {10.1109/lics56636.2023.10175685}
}