On Computability of Data Word Functions Defined by Transducers @ ETAPS 2021

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
Apr 1, 2021 6:00 PM
Location
Online
Due to the worldwide outbreak of CoViD-19, ETAPS 2020 has been cancelled. I thus present this work at the 2021 edition of the conference.

Related