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.
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.
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