Regular functions of infinite words are (partial) functions realized by deterministic two-way transducers with infinite look-ahead. Equivalently, Alur et. al. have shown that they correspond to functions realized by deterministic Muller streaming string transducers, and to functions defined by MSO-transductions. Regular functions are however not computable in general (for a classical extension of Turing computability to infinite inputs), and we consider in this paper the class of deterministic regular functions of infinite words, realized by deterministic two-way transducers without look-ahead. We prove that it is a well-behaved class of functions: they are computable, closed under composition, characterized by the guarded fragment of MSO-transductions, by deterministic B\"uchi streaming string transducers, by deterministic two-way transducers with finite look-ahead, and by finite compositions of sequential functions and one fixed basic function called map-copy-reverse.
翻译：无限单词的常规功能是( 部分) 由具有无限外观的定型双向导体实现的定型双向导体函数。 同等地, Alur等人已经表明,它们与确定性 Muller 流式导体所实现的功能相对应, 也与 MSO 传输系统所定义的函数相对应。 然而, 通常功能一般而言无法计算( 就图解可乘性和无限输入的典型延伸而言 ), 我们在本文件中认为, 由没有外观的定型双向导体所实现的定型常规功能无穷无穷的定型双向导体函数类别。 我们证明, 它是一个妥善的功能类别: 它们是可计算、 封闭在构件下, 其特征为 MSO- 传输系统受守制的碎片, 由确定性 B\\“ uchi 流式流式导体导体的定型双向导体, 外观有限的定型双向导体, 由有限的连续函数构成和固定的基本功能称为地图- 反形。
相关内容
微信扫码咨询专知VIP会员