← 研踪 PaperTrailarXiv: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
摘要
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
观测到的版本
相邻记录可能跳过中间版本;首次发现 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.
查看此版本解读 →查看此版本原文 ↗