← All problems
Unverified

Monotone regular functions

A regular function is given by a deterministic 2way transducer: a deterministic 2way automaton with outputs. Over the word w∈Σ∗w\in \Sigma^* such an automaton has an input tape with content ⊢w⊣{\vdash} w {\dashv} and can move left and right in a read-only fashion (accepting runs have to end on ⊣\dashv). On every transition an output word in Γ∗\Gamma^* is written on a right-only output tape. Such a machine realizes a partial function f:Σ∗→Γ∗f:\Sigma^*\rightarrow\Gamma^*, defined on words with an accepting run. Such a function ff is monotone if for any u,v∈Σ∗u,v\in\Sigma^*, if u≤vu\leq v then f(u)≤f(v)f(u)\leq f(v), where ≤\leq denotes the prefix order. A sequential 2way transducer is a syntactic restriction of deterministic transducers where no transition is allowed on symbol ⊣\dashv. Such a machine necessarily realizes a monotone function since the run over word uu is a prefix of the run over word uvuv. </p> Question: Can every monotone regular function be realized by a sequential 2way transducer?

Coming soon

Organizer

Boyuan Wang portraitBoyuan Wang
Minghan Wang portraitMinghan Wang
Bochao Li portraitBochao Li
Hongwei Hu portraitHongwei Hu