On Computability of Data Word Functions Defined by Transducers @ HIGHLIGHTS 2020

Abstract

In this talk, 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 PTime.

Date
Sep 17, 2020 11:11 AM — 11:18 AM
Location
Online

I gave a brief talk on this work at HIGHLIGHTS 2020, which happened online this year. We were also asked to make a poster. This talk has been recorded:

Related