论文标题
关于传感器定义的数据单词函数的可计算性
On Computability of Data Word Functions Defined by Transducers
论文作者
论文摘要
在本文中，我们研究了在无限字母（数据欧米茄字）上合成无限单词的可计算函数的问题。可计算性的概念是通过带有无限输入的图灵机来定义的，这些计算机可以在极限内产生相应的无限输出。我们使用配备寄存器的非确定性传感器，带有输出的寄存器自动机的扩展名来指定功能。这样的传感器可能无法定义函数，而是更一般的数据欧米茄字关系，我们表明，测试给定传感器是否定义函数是PSPACE完整的。然后，给定某些寄存器换能器定义的函数，我们表明它是可确定的（又是Pspace-complete）是否可以计算。至于已知的有限字母案例，我们表明寄存器换能器定义的功能的可计算性和连续性重合，并显示如何确定连续性。我们还定义了一个子类，在多项式时间内可以解决这些问题。
In this paper, we investigate the problem of synthesizing computable functions of infinite words over an infinite alphabet (data omega-words). The notion of computability is defined through Turing machines with infinite inputs which can produce the corresponding infinite outputs in the limit. We use non-deterministic transducers equipped with registers, an extension of register automata with outputs, to specify functions. Such transducers may not define functions but more generally relations of data omega-words, and we show that it is PSpace-complete to test whether a given transducer defines a function. Then, given a function defined by some register transducer, we show that it is decidable (and again, PSpace-complete) whether such function is computable. As for the known finite alphabet case, we show that computability and continuity coincide for functions defined by register transducers, and show how to decide continuity. We also define a subclass for which those problems are solvable in polynomial time.
