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