On reversible transducers
From MaRDI portal
Abstract: Deterministic two-way transducers define the robust class of regular functions which is, among other good properties, closed under composition. However, the best known algorithms for composing two-way transducers cause a double exponential blow-up in the size of the inputs. In this paper, we introduce a class of transducers for which the composition has polynomial complexity. It is the class of reversible transducers, for which the computation steps can be reversed deterministically. While in the one-way setting this class is not very expressive, we prove that any two-way transducer can be made reversible through a single exponential blow-up. As a consequence, we prove that the composition of two-way transducers can be done with a single exponential blow-up in the number of states. A uniformization of a relation is a function with the same domain and which is included in the original relation. Our main result actually states that we can uniformize any non-deterministic two-way transducer by a reversible transducer with a single exponential blow-up, improving the known result by de Souza which has a quadruple exponential complexity. As a side result, our construction also gives a quadratic transformation from copyless streaming string transducers to two-way transducers, improving the exponential previous bound.
Recommendations
Cited in
(23)- From two-way transducers to regular function expressions
- Transducers and repetitions
- Uniformisation of two-way transducers
- Register Transducers Are Marble Transducers
- The many facets of string transducers (invited talk)
- Untwisting two-way transducers in elementary time
- Robustness analysis of string transducers
- Transducers with Origin Information
- Sistemi A Trasformazioni Reversibili
- From two-way transducers to regular function expressions
- Reversible pushdown transducers
- Transducing reversibly with finite state machines
- Transducing reversibly with finite state machines
- Weighted two-way transducers
- Efficient construction of reversible transducers from regular transducer expressions
- Implicit automata in -calculi. III: Affine planar string-to-string functions
- Single-use automata and transducers for infinite alphabets
- Reversible transducers over infinite words
- Finite-valued streaming string transducers
- Finite-valued streaming string transducers
- Slightly nonlinear higher-order tree transducers
- Reversible pebble transducers
- Two-way pebble transducers for partial functions and their composition
This page was built for publication: On reversible transducers
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111445)
