A uniformizer of a binary relation is a function whose graph is contained in the relation and which is defined on the same domain as the relation. It is known that any rational relation of infinite words, i.e. a relation given as a transducer, admits a rational uniformizer. Although rational, those uniformizers are not necessarily well-behaved, in the sense that the $i$th letter of the output word may depend on the whole infinite input word. In other words, those uniformizers might not be continuous (for the Cantor topology). This paper addresses the question of whether rational relations of infinite words can be uniformized by continuous functions. On the negative side, continuous uniformizers might not exist in general and we prove that deciding their existence is algorithmically impossible. On the positive side, we exhibit a large class of rational relations of infinite words, called weakly deterministic rational relations, for which deciding whether a relation in this class admits a continuous uniformizer is an ExpTime-c problem. This class includes the known classes of deterministic rational relations and automatic relations of infinite words. As an application of the previous result, and by exploiting a connection between computability and continuity for rational functions of infinite words, we show a result on the synthesis of computable functions from specifications given as weakly deterministic rational relations. In particular, we show that deciding the existence of a computable uniformizer is ExpTime-c and if there is one, it is possible to effectively synthesize a deterministic two-way transducer computing it. This generalizes the classical setting of Church synthesis to asynchronous implementations which can arbitrarily delay the production of their output signals.
翻译:二进制关系的统一是一个函数,其图表包含在关系中,并且定义与关系相同的领域。众所周知,任何无限单词的合理关系,即作为转换器提供的某种关系,都承认合理的统一。虽然是合理的,但那些统一器不一定很好地遵守,因为产出单词的美元字母可能取决于整个无限输入单词。换句话说,这些统一器可能不是连续的(对坎托尔的地形学来说)。本文探讨无限单词的合理关系能否通过连续功能统一的问题。在负面方面,连续的统一器可能不存在,我们证明确定其存在是不可能的。在积极方面,我们展示了无限单词的大规模合理关系,要求薄弱的确定性理性关系可能取决于整个无限输入单词。为此,这些统一器可能不是连续的(对坎托尔的地形学来说)。这一类包括已知的确定性合理关系类别以及一个无限的信号的自动关系。在消极方面,持续的统一器可能存在,而我们通过运用前的精确性分析结果来展示它们之间的可变性关系,这是我们所显示的可变化性结果。