跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2605.09435 · v2

Star Complexity of Parikh Images of Languages over Infinite Alphabets

首次提交 2026-05-10 17:16
版本更新 2026-11-19 20:04
雷达观测 2026-11-20 16:53
arXiv ↗PDF ↗

摘要

Parikh's theorem identifies the commutative images of regular and context-free languages over finite alphabets. We study the commutative images of quasi-regular and quasi-context-free languages over infinite alphabets, these are the languages that are accepted by the corresponding automata models augmented with registers. Over finite alphabets commutative images of regular languages are known to be precisely the semilinear sets, over infinite alphabets the corresponding algebraic sets are called rational sets of data vectors. In contrast to semilinear sets, nesting stars in rational sets add expressive power and thus star-height is a measure of complexity for this sets. It was previously established that languages accepted by one-register automata or one-register binary branching context-free grammars have rational commutative images. We refine this result by proving that the star-height of the commutative image of any one-register automaton is at most two. Using this extension, we prove rationality for all one-register context-free grammars, with arbitrary branching degree. Furthermore, we show that quasi-regular languages can have irrational commutative images already for a language accepted by a three-register automaton. Finally, we show that quasi-context-free languages can have commutative images that are different from the commutative image of any quasi-regular language, where the separation is witnessed again with three registers. Thus we conclude that Parikh's theorem fails over infinite alphabets for automata with registers.

作者备注:Full version of LICS 2026

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

本站首次收录为 v2,暂无更早版本可对照。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v2 · 2026-11-19 20:04 · 最新观测版本

Star Complexity of Parikh Images of Languages over Infinite Alphabets

Parikh's theorem identifies the commutative images of regular and context-free languages over finite alphabets. We study the commutative images of quasi-regular and quasi-context-free languages over infinite alphabets, these are the languages that are accepted by the corresponding automata models augmented with registers. Over finite alphabets commutative images of regular languages are known to be precisely the semilinear sets, over infinite alphabets the corresponding algebraic sets are called rational sets of data vectors. In contrast to semilinear sets, nesting stars in rational sets add expressive power and thus star-height is a measure of complexity for this sets. It was previously established that languages accepted by one-register automata or one-register binary branching context-free grammars have rational commutative images. We refine this result by proving that the star-height of the commutative image of any one-register automaton is at most two. Using this extension, we prove rationality for all one-register context-free grammars, with arbitrary branching degree. Furthermore, we show that quasi-regular languages can have irrational commutative images already for a language accepted by a three-register automaton. Finally, we show that quasi-context-free languages can have commutative images that are different from the commutative image of any quasi-regular language, where the separation is witnessed again with three registers. Thus we conclude that Parikh's theorem fails over infinite alphabets for automata with registers.

查看此版本解读 →查看此版本原文 ↗