Options
Efficient Construction of Reversible Transducers from Regular Transducer Expressions
Journal
Proceedings - Symposium on Logic in Computer Science
ISSN
10436871
Date Issued
2022-08-02
Author(s)
Dartois, Luc
Gastin, Paul
Govind, R.
Krishna, Shankara Narayanan
Abstract
The class of regular transformations has several equivalent characterizations such as functional MSO transductions, deterministic two-way transducers, streaming string transducers, as well as regular transducer expressions (RTE). For algorithmic applications, it is very common and useful to transform a specifcation, here, an RTE, to a machine, here, a transducer. In this paper, we give an efcient construction of a two-way reversible transducer (2RFT) equivalent to a given RTE. 2RFTs form a well behaved class of transducers which are deterministic and codeterministic (hence allows evaluation in linear time w.r.t. the input word), and where composition has only polynomial complexity. As a signifcant complexity improvement over existing techniques, we give the frst elementary procedure for translating RTEs to machines. For full RTE, the constructed 2RFT has size doubly exponential in the size of the expression. If the RTE does not use Hadamard product or chained-star, the constructed 2RFT has size exponential in the size of the RTE.
Subjects