You are not logged in | Log in

The class of regular functions from infinite words to infinite words is

characterised by MSO-transducers, streaming ω-string transducers

(transducers with registers) as well as deterministic two-way

transducers with regular look-ahead. In their one-way restriction, the

latter transducers define the class of rational functions.

Computability of functions over ω-words is defined through deterministic

type 2 Turing machines, which have an (infinite) input tape, several

working tapes, and a write-only output tape. Then the output of such a

machine over an input ω-word, is the ω-word eventually produced along

the run on the output tape.

While it is easy to see that computability entails continuity, the

converse does not hold in general. We show however that in the case of

regular functions, continuity and computability are equivalent. We give

a generic characterisation of continuity for functions preserving

regular languages by inverse image. Using this we are able to decide

computability of rational functions in NLogSpace (it was already known

to be in PTime by Prieur) and regular functions in PSpace.

Computability and continuity of regular functions over ω-words