一句话：研究寄存器转导器定义的数据ω-词函数，证明连续性与可计算性等价，并给出判定问题的PSpace复杂度
论文研究无限字母表上无限词（数据ω-词）函数的可计算性问题。可计算性由能接收无限输入并在极限产生无限输出的图灵机定义；规格用带寄存器与输出的非确定转导器描述，并允许在更新寄存器时猜测任意数据值。针对数据ω-词函数，作者提出“下一字母问题”作为充分条件，在该条件下（一致）可计算性与（一致）连续性重合。论文考察两类数据域：一般寡态（oligomorphic）数据域以及自然数线性序(N,<)。主要结果包括：关系是否为函数、下一字母问题均可判定，从而得到连续性与可计算性的等价；给出（一致）连续性的刻画，并证明相关判定问题在(N,<)及一大类寡态数据域（如(Q,<)）上是PSpace完全的。
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 describe specifications. Being non-deterministic, such transducers may not define functions but more generally relations of data $\omega$-words. In order to increase the expressive power of these machines, we even allow guessing of arbitrary data values when updating their registers. For functions over data $\omega$-words, we identify a sufficient condition (the possibility of determining the next letter to be outputted, which we call next letter problem) under which computability (resp. uniform computability) and continuity (resp. uniform continuity) coincide. We focus on two kinds of data domains: first, the general setting of oligomorphic data, which encompasses any data domain with equality, as well as the setting of rational numbers with linear order; and second, the set of natural numbers equipped with linear order. For both settings, we prove that functionality, i.e. determining whether the relation recognized by the transducer is actually a function, is decidable. We also show that the so-called next letter problem is decidable, yielding equivalence between (uniform) continuity and (uniform) computability. Last, we provide characterizations of (uniform) continuity, which allow us to prove that these notions, and thus also (uniform) computability, are decidable. We even show that all these decision problems are PSpace-complete for $(\mathbb{N},<)$ and for a large class of oligomorphic data domains, including for instance $(\mathbb{Q},<)$.
@article{paperbot1676,
title = {Computability of Data-Word Transductions over Different Data Domains},
author = {Léo Exibard and Emmanuel Filiot and Nathan Lhote and Pierre-Alain Reynier},
journal = {Logical Methods in Computer Science},
volume = {Volume 18, Issue 3},
year = {2022},
doi = {10.46298/lmcs-18(3:9)2022}
}