一句话：提出首个初等过程，将正则转换器表达式高效构造为等价的二向可逆转换器，并给出双指数/指数复杂度上界。
正则转换（regular transformations）有多种等价刻画，如函数式 MSO 转换、确定二向转换器、流式字符串转换器以及正则转换器表达式（RTE）。实际应用常需将 RTE 规格转换为机器。本文提出一种高效构造，把给定 RTE 转换为等价的二向可逆转换器（2RFT）。2RFT 是确定且余确定的良性转换器类，可在输入词长度上线性时间求值，组合复杂度仅为多项式。作为对已有技术的显著复杂度改进，作者给出首个将 RTE 翻译为机器的初等过程：对完整 RTE，构造出的 2RFT 大小为表达式大小的双指数；若 RTE 不使用 Hadamard 积或 chained-star，则大小为指数。
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 specification, here, an RTE, to a machine, here, a transducer. In this paper, we give an efficient 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 co-deterministic (hence allows evaluation in linear time w.r.t. the input word), and where composition has only polynomial complexity. As a significant complexity improvement over existing techniques, we give the first 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.
DOI 原文 · arXiv · PDF（开放获取） · DBLP
@inproceedings{DartoisGGK22,
title = {Efficient Construction of Reversible Transducers from Regular Transducer Expressions},
author = {Luc Dartois and Paul Gastin and Govind and Krishna},
booktitle = {LICS},
year = {2022},
doi = {10.1145/3531130.3533364}
}