Léo Exibard ; Emmanuel Filiot ; Nathan Lhote ; Pierre-Alain Reynier - Computability of Data-Word Transductions over Different Data Domains

lmcs:7104 - Logical Methods in Computer Science, July 29, 2022, Volume 18, Issue 3 - https://doi.org/10.46298/lmcs-18(3:9)2022
Computability of Data-Word Transductions over Different Data DomainsArticle

Authors: Léo Exibard ; Emmanuel Filiot ; Nathan Lhote ; Pierre-Alain Reynier

    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},<)$.


    Volume: Volume 18, Issue 3
    Published on: July 29, 2022
    Accepted on: April 5, 2022
    Submitted on: January 19, 2021
    Keywords: Computer Science - Formal Languages and Automata Theory,Computer Science - Logic in Computer Science
    Funding:
      Source : OpenAIRE Graph
    • Challenges for Logic, Transducers and Automata; Funder: French National Research Agency (ANR); Code: ANR-16-CE40-0007
    • Efficient Techniques and Tools for Verification and Synthesis of Real-Time Systems; Funder: French National Research Agency (ANR); Code: ANR-18-CE40-0015

    Consultation statistics

    This page has been seen 2079 times.
    This article's PDF has been downloaded 566 times.