Félix Baschenis ; Olivier Gauwin ; Anca Muscholl ; Gabriele Puppis - One-way definability of two-way word transducers

lmcs:3697 - Logical Methods in Computer Science, December 7, 2018, Volume 14, Issue 4 - https://doi.org/10.23638/LMCS-14(4:22)2018
One-way definability of two-way word transducersArticle

Authors: Félix Baschenis ; Olivier Gauwin ; Anca Muscholl ; Gabriele Puppis

    Functional transductions realized by two-way transducers (or, equally, by streaming transducers or MSO transductions) are the natural and standard notion of "regular" mappings from words to words. It was shown in 2013 that it is decidable if such a transduction can be implemented by some one-way transducer, but the given algorithm has non-elementary complexity. We provide an algorithm of different flavor solving the above question, that has doubly exponential space complexity. In the special case of sweeping transducers the complexity is one exponential less. We also show how to construct an equivalent one-way transducer, whenever it exists, in doubly or triply exponential time, again depending on whether the input transducer is sweeping or two-way. In the sweeping case our construction is shown to be optimal.


    Volume: Volume 14, Issue 4
    Published on: December 7, 2018
    Accepted on: October 9, 2018
    Submitted on: June 7, 2017
    Keywords: Computer Science - Formal Languages and Automata Theory,Computer Science - Logic in Computer Science
    Funding:
      Source : OpenAIRE Graph
    • Extensions of Stream Processing; Funder: French National Research Agency (ANR); Code: ANR-13-JS02-0010
    • Challenges for Logic, Transducers and Automata; Funder: French National Research Agency (ANR); Code: ANR-16-CE40-0007

    1 Document citing this article

    Consultation statistics

    This page has been seen 1154 times.
    This article's PDF has been downloaded 540 times.