Monotone regular functions
A regular function is given by a deterministic 2way transducer: a deterministic 2way automaton with outputs. Over the word such an automaton has an input tape with content and can move left and right in a read-only fashion (accepting runs have to end on ). On every transition an output word in is written on a right-only output tape. Such a machine realizes a partial function , defined on words with an accepting run. Such a function is monotone if for any , if then , where denotes the prefix order. A sequential 2way transducer is a syntactic restriction of deterministic transducers where no transition is allowed on symbol . Such a machine necessarily realizes a monotone function since the run over word is a prefix of the run over word . </p> Question: Can every monotone regular function be realized by a sequential 2way transducer?
