On Reversible Transducers
From MaRDI portal
Publication:5111445
DOI10.4230/LIPICS.ICALP.2017.113zbMATH Open1442.68089arXiv1702.07157OpenAlexW2593298558MaRDI QIDQ5111445FDOQ5111445
Paulin Fournier, Ismaël Jecker, Luc Dartois, Nathan Lhote
Publication date: 27 May 2020
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.
Full work available at URL: https://arxiv.org/abs/1702.07157
Cited In (9)
- Register Transducers Are Marble Transducers
- Title not available (Why is that?)
- Transducers with Origin Information
- Sistemi A Trasformazioni Reversibili
- Transducing reversibly with finite state machines
- Efficient construction of reversible transducers from regular transducer expressions
- Reversible pushdown transducers
- Transducers and repetitions
- Weighted two-way transducers
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)
