Orbits of linear maps and regular languages
Orbits of linear maps and regular languages
复制标题
线性映射和正则语言的轨道
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
M. Vyalyi
中科院分区：
文献类型：
--
作者：
S. Tarasov;M. Vyalyi
建立了线性映射的轨道击中多面体集问题与正则语言和二进制字排列语言的交问题（$$P_mathbb{B}$$-可实现性问题）的等价性。这两个问题的可判定性是目前未知的，第一个是一个简单的推广著名的Skolem问题和线性递归序列理论中的非负性问题。
The equivalence is established of the problem of hitting a polyhedral set by the orbit of a linear map and the intersection of a regular language and a language of permutations of binary words ($$P_mathbb{B}$$-realizability problem). The decidability of the both problems is presently unknown, and the first one is a straightforward generalization of the famous Skolem problem and the nonnegativity problem in the theory of linear recurrent sequences.