Name
Abstract | ||
|---|---|---|
The class of regular functions from infinite words to infinite words is characterised by MSO-transducers, streaming $\omega$-string transducers as well as deterministic two-way transducers with look-ahead. In their one-way restriction, the latter transducers define the class of rational functions. This paper proposes a decision procedure for the fundamental question : given a regular function $f$, is $f$ computable (by a Turing machine with infinite input)? For regular functions, we show that computability is equivalent to continuity, and therefore the problem boils down to deciding continuity. We establish a generic characterisation of continuity for functions preserving regular languages under inverse image (such as regular functions). We exploit this characterisation to show the decidability of continuity (and hence computability) of rational functions in \textsc{NLogSpace} (it was already known to be in \textsc{PTime} by Prieur), and of regular functions. |
Year | Venue | DocType |
|---|---|---|
2019 | CoRR | Journal |
Volume | Citations | PageRank |
abs/1906.04199 | 0 | 0.34 |
References | Authors | |
0 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Vrunda Dave | 1 | 6 | 2.83 |
| Emmanuel Filiot | 2 | 217 | 24.98 |
| Shankara Narayanan Krishna | 3 | 243 | 42.57 |
| Nathan Lhote | 4 | 0 | 2.03 |