paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Transducers of polynomial growth

多项式增长的换能器
LICS Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science2022匹配度 1/10 · 该论文是纯自动机理论/逻辑方向的综述，讨论 polyregular 函数（有限状态转换器的多项式输出）的等价定义与判定问题，与用户关注的静态分析、浮点程序分析、贝叶斯程序分析以及 LLM/Agent 交叉方向均无直接交集，既不涉及程序分析的理论与工程实现，也不涉及机器学习系统或基准测试。引用 24 inbox
Mikolaj Bojanczyk
逻辑与自动机
crossref: 2026-09-12dblp: 2026-09-12

AI 速览

一句话：综述 polyregular 函数（多项式规模输出的字符串函数）的五种等价定义、判定问题与受限子类。

本文综述近年来关于 polyregular 函数的研究。polyregular 函数是一类输出规模为多项式的字符串到字符串函数，可由有限状态模型定义，并在自动机理论、程序语言和逻辑中有多种等价定义。文章给出其中五种等价定义，并为大多数等价性提供自包含证明，从而统一比较这些不同视角。此外还讨论了该函数类的判定问题，以及若干受限子类。整体上，这是一篇面向自动机与形式语言理论的理论综述，重点在于等价刻画的整理与证明，而非实验评估。

问题
如何刻画具有多项式规模输出的字符串到字符串函数类 polyregular functions，并理解其来自自动机、程序语言和逻辑的多种等价定义。
方法
综述近期结果，系统给出五种等价定义，并为大部分等价性提供自包含证明，同时讨论判定问题和受限子类。
评估
属于理论综述与机器化/数学证明式研究，以统一证明和比较等价定义为主要评估方式，不涉及实证实验。
原文摘要（Abstract）

The polyregular functions are a class of string-to-string functions that have polynomial size outputs, and which can be defined using finite state models. There are many equivalent definitions of this class, with roots in automata theory, programming languages and logic. This paper surveys recent results on polyregular functions. It presents five of the equivalent definitions, and gives self-contained proofs for most of the equivalences. Decision problems as well as restricted subclasses of the polyregular functions are also discussed.

链接与引用

DOI 原文 · DBLP

BibTeX 
@inproceedings{Bojanczyk22,
  title = {Transducers of polynomial growth},
  author = {Mikolaj Bojanczyk},
  booktitle = {LICS},
  year = {2022},
  doi = {10.1145/3531130.3533326}
}