文章基本信息

标题：Minimizing Resources of Sweeping and Streaming String Transducers
本地全文：下载
作者：F{\'e}lix Baschenis ; Olivier Gauwin ; Anca Muscholl 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2016
卷号：55
页码：114:1-114:14
DOI：10.4230/LIPIcs.ICALP.2016.114
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We consider minimization problems for natural parameters of word transducers: the number of passes performed by two-way transducers and the number of registers used by streaming transducers. We show how to compute in ExpSpace the minimum number of passes needed to implement a transduction given as sweeping transducer, and we provide effective constructions of transducers of (worst-case optimal) doubly exponential size. We then consider streaming transducers where concatenations of registers are forbidden in the register updates. Based on a correspondence between the number of passes of sweeping transducers and the number of registers of equivalent concatenation-free streaming transducers, we derive a minimization procedure for the number of registers of concatenation-free streaming transducers.
关键词：word transducers; streaming; 2-way; sweeping transducers; minimization