One-way definability of two-way word transducers

Félix Baschenis, Olivier Gauwin, Anca Muscholl, Michael Benedikt

Abstract

Functional transductions realized by two-way transducers are the standard notion of "regular" mappings from words to words. While more powerful than one-way transducers, they are significantly harder to implement efficiently. This paper provides a landmark algorithm to decide if a two-way transduction can be simplified into a one-way version. By reducing the decision complexity from non-elementary to doubly exponential space (2-EXPSPACE), the authors provide a practical theoretical framework for optimizing string transformations and prove optimality for sweeping transducers.

The Efficiency Gap: One-way vs. Two-way Transducers

In formal language theory, transducers are machines that translate input strings into output strings. One-way transducers read input once from left to right, making them ideal for high-speed streaming data. In contrast, two-way transducers can move their reading head back and forth across the input multiple times.

A visualization of a two-way transducer run, showing the reading head moving back and forth across input positions.

While two-way machines can describe a broader range of functions, they are computationally expensive. A fundamental question is whether a given two-way transducer has an equivalent, more efficient one-way counterpart. Previous solutions to this "one-way definability" problem were known to be decidable but had non-elementary complexity—essentially a "tower of exponentials" that rendered them computationally useless.

Methodology: Structural Decompositions and Periodicity

The authors achieve their complexity breakthrough by employing sophisticated tools from automata theory and word combinatorics. A central technique involves Crossing Sequences, which track the set of states a machine is in every time it crosses a specific point in the input.

Structural decomposition of a run over an interval, illustrating how crossing sequences track state transitions at boundaries.

To manage the complexity of two-way runs, the paper introduces B-Decompositions. This novel approach breaks down complex runs into "diagonals" (behaving like one-way runs) and "blocks" (handling periodic, reversible parts). The core insight is the Periodicity Requirement: two-way movement is only reducible to one-way movement if the output produced during reversals is highly periodic. If a machine produces complex, non-repeating data while moving backward, a one-way machine cannot replicate the behavior because it cannot "un-read" the input.

Key Results and Complexity

The paper establishes new upper bounds for both deciding definability and constructing the resulting one-way machines:

  • Decision Complexity: The problem is shown to be in 2-EXPSPACE for general transducers and 1-EXPSPACE for sweeping transducers (machines that only change direction at input boundaries).
  • Construction: If a one-way version exists, it can be constructed in 3-EXPTIME for general cases and 2-EXPTIME for sweeping cases.
  • Optimality: For the class of sweeping transducers, the authors prove that their doubly exponential construction is optimal.

These results apply specifically to functional transducers—those that produce exactly one output for each input. The authors note that for non-functional transducers, the problem remains undecidable.

Conclusion and Future Directions

This research significantly closes the gap between theoretical decidability and practical algorithmic bounds. While 2-EXPSPACE is a massive improvement over non-elementary complexity, a gap remains between this upper bound and the known PSPACE lower bound. Future work may focus on closing this gap or exploring restricted subclasses of non-functional transducers where the problem might become decidable.

Summary updated

Abstract

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.
BibTeX
@inproceedings{baschenis2018one,
  author = {Félix Baschenis and Olivier Gauwin and Anca Muscholl and Michael Benedikt},
  title = {{One-way definability of two-way word transducers}},
  booktitle = {Logical},
  year = {2018},
  doi = {10.23638/lmcs-14(4:22)2018},
}

Loading related content...

Figure