LIPIcs.ICALP.2016.114.pdf
- Filesize: 0.52 MB
- 14 pages
Document
Minimizing Resources of Sweeping and Streaming String Transducers
Authors
-
Part of:
Volume:
43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Colloquium on Automata, Languages, and Programming (ICALP) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2016-08-23
Cite As Get BibTex
Félix Baschenis, Olivier Gauwin, Anca Muscholl, and Gabriele Puppis. Minimizing Resources of Sweeping and Streaming String Transducers. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 114:1-114:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.ICALP.2016.114
Abstract
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.
Subject Classification
Keywords
- word transducers
- streaming
- 2-way
- sweeping transducers
- minimization
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
A. V. Aho and J. D. Ullman. A characterization of two-way deterministic classes of languages. J. Comput. Syst. Sci., 4(6):523-538, 1970.
- R. Alur and P. Cerný. Expressiveness of streaming string transducers. In FSTTCS, volume 8 of LIPIcs, pages 1-12. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2010. URL: http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2010.1.
-
R. Alur and L. D'Antoni. Streaming tree transducers. In ICALP, volume 7392 of LNCS, pages 42-53. Springer, 2012.
-
R. Alur and M. Raghothaman. Decision problems for additive regular functions. In ICALP, volume 7966 of LNCS, pages 37-48. Springer, 2013.
- F. Baschenis, O. Gauwin, A. Muscholl, and G. Puppis. One-way definability of sweeping transducers. In FSTTCS, volume 45 of LIPIcs, pages 178-191. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2015.178.
- O. Carton and L. Dartois. Aperiodic two-way transducers and FO-transductions. In CSL, LIPIcs, pages 160-174. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.CSL.2015.160.
-
L. Daviaud, P.-A. Reynier, and J.-M. Talbot. A generalised twinning property for minimisation of cost register automata. In LICS. IEEE Computer Society, 2016.
-
J. Engelfriet and H. J. Hoogeboom. MSO definable string transductions and two-way finite-state transducers. ACM Trans. Comput. Logic, 2:216-254, 2001.
-
E. Filiot. Logic-automata connections for transformations. In ICLA, pages 30-57, 2015.
-
E. Filiot, O. Gauwin, P.-A. Reynier, and F. Servais. From two-way to one-way finite state transducers. In LICS, pages 468-477. IEEE Computer Society, 2013.
- E. Filiot, S. N. Krishna, and A. Trivedi. First-order definable string transformations. In FSTTCS, volume 29 of LIPIcs, pages 147-159. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2014. URL: http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2014.147.
-
J. C. Shepherdson. The reduction of two-way automata to one-way automata. IBM Journal of Research and Development, 3(2):198-200, 1959.
-
M. Sipser. Lower bounds on the size of sweeping automata. In STOC, pages 360-364. ACM, 1979.