论文标题
持续有理功能是确定性的常规
Continuous rational functions are deterministic regular
论文作者
论文摘要
如果单词到字函数可以由非确定性的单向传感器实现，则是合理的。在有限的单词上，任何有理函数都是常规的，即可以通过确定性的双向传感器进行计算，也可以通过确定性流式的字符串传感器（一个单向自动机操作字符串登录）来计算。 该结果不再适用于无限单词，因为非确定性的单向传感器可以猜测并检查其运行，例如无限多种模式出现的属性，这对于确定性机器是不可能的。在本文中，我们确定了无限单词的理性函数类别，这些函数也可以通过确定性的双向传感器来计算。它与连续的理性函数类别相吻合，因此可以决定该属性。这解决了Dave等人的先前论文中提出的一个空旷的问题。
A word-to-word function is rational if it can be realized by a non-deterministic one-way transducer. Over finite words, it is a classical result that any rational function is regular, i.e. it can be computed by a deterministic two-way transducer, or equivalently, by a deterministic streaming string transducer (a one-way automaton which manipulates string registers). This result no longer holds for infinite words, since a non-deterministic one-way transducer can guess, and check along its run, properties such as infinitely many occurrences of some pattern, which is impossible for a deterministic machine. In this paper, we identify the class of rational functions over infinite words which are also computable by a deterministic two-way transducer. It coincides with the class of rational functions which are continuous, and this property can thus be decided. This solves an open question raised in a previous paper of Dave et al.
