paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Parikh’s theorem for infinite alphabets

无限字母表上的 Parikh 定理
LICS 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)2021匹配度 1/10 · 该论文研究无限字母表下寄存器自动机/文法的交换像与 Parikh 定理推广,属于纯形式语言与自动机理论,未涉及静态分析、LLM/Agent、浮点程序分析或贝叶斯程序分析等用户核心方向。引用 0 inbox
Piotr Hofman, Marta Juzepczuk, Slawomir Lasota, Mohnish Pattathurajan
crossref: 2026-09-12

AI 速览

一句话:证明单寄存器自动机/文法语言的交换像总是有理的,并指出未必半线性,猜想多寄存器情形类似。

本文研究无限字母表下寄存器自动机与文法所识别语言的交换像(Parikh 像)。作者将半线性集与有理集的概念推广到该设定,允许用轨道有限并替代通常的有限并。主要结果是:单寄存器自动机语言的交换像不一定半线性,但一定是有理的;进一步,单寄存器上下文无关语言的交换像也是有理的,因此与单寄存器自动机语言在交换意义下等价。作者据此猜想,对任意多寄存器的自动机和文法,类似的有理性结论仍然成立。

问题
在无限字母表与寄存器自动机/文法框架下,经典 Parikh 定理所涉及的交换像的半线性/有理性是否仍然成立?
方法
把半线性集和有理集扩展到轨道有限并,并分析单寄存器自动机及单寄存器上下文无关文法的交换像。
评估
通过理论证明确立单寄存器自动机的交换像有理性但非必然半线性,并将其提升到单寄存器文法;多寄存器情形留作猜想。
原文摘要(Abstract)

We investigate commutative images of languages recognised by register automata and grammars. Semi-linear and rational sets can be naturally extended to this setting by allowing for orbit-finite unions instead of only finite ones. We prove that commutative images of languages of one-register automata are not always semi-linear, but they are always rational. We also lift the latter result to grammars: commutative images of one- register context-free languages are rational, and in consequence commutatively equivalent to register automata. We conjecture analogous results for automata and grammars with arbitrarily many registers.

链接与引用

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

BibTeX
@inproceedings{paperbot6201,
  title = {Parikh’s theorem for infinite alphabets},
  author = {Piotr Hofman and Marta Juzepczuk and Slawomir Lasota and Mohnish Pattathurajan},
  booktitle = {LICS},
  year = {2021},
  doi = {10.1109/lics52264.2021.9470626}
}