Minimizing Resources of Sweeping and Streaming String Transducers

Authors Félix Baschenis, Olivier Gauwin, Anca Muscholl, Gabriele Puppis



PDF
Thumbnail PDF

File

LIPIcs.ICALP.2016.114.pdf
  • Filesize: 0.52 MB
  • 14 pages

Document Identifiers

Author Details

Félix Baschenis
Olivier Gauwin
Anca Muscholl
Gabriele Puppis

Cite AsGet 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.
Keywords
  • word transducers
  • streaming
  • 2-way
  • sweeping transducers
  • minimization

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. 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. Google Scholar
  2. 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.
  3. R. Alur and L. D'Antoni. Streaming tree transducers. In ICALP, volume 7392 of LNCS, pages 42-53. Springer, 2012. Google Scholar
  4. R. Alur and M. Raghothaman. Decision problems for additive regular functions. In ICALP, volume 7966 of LNCS, pages 37-48. Springer, 2013. Google Scholar
  5. 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.
  6. 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.
  7. 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. Google Scholar
  8. J. Engelfriet and H. J. Hoogeboom. MSO definable string transductions and two-way finite-state transducers. ACM Trans. Comput. Logic, 2:216-254, 2001. Google Scholar
  9. E. Filiot. Logic-automata connections for transformations. In ICLA, pages 30-57, 2015. Google Scholar
  10. 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. Google Scholar
  11. 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.
  12. J. C. Shepherdson. The reduction of two-way automata to one-way automata. IBM Journal of Research and Development, 3(2):198-200, 1959. Google Scholar
  13. M. Sipser. Lower bounds on the size of sweeping automata. In STOC, pages 360-364. ACM, 1979. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail