On the Decomposition of Finite-Valued Streaming String Transducers

Authors Paul Gallot, Anca Muscholl, Gabriele Puppis, Sylvain Salvati



PDF
Thumbnail PDF

File

LIPIcs.STACS.2017.34.pdf
  • Filesize: 0.56 MB
  • 14 pages

Document Identifiers

Author Details

Paul Gallot
Anca Muscholl
Gabriele Puppis
Sylvain Salvati

Cite AsGet BibTex

Paul Gallot, Anca Muscholl, Gabriele Puppis, and Sylvain Salvati. On the Decomposition of Finite-Valued Streaming String Transducers. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 34:1-34:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.STACS.2017.34

Abstract

We prove the following decomposition theorem: every 1-register streaming string transducer that associates a uniformly bounded number of outputs with each input can be effectively decomposed as a finite union of functional 1-register streaming string transducers. This theorem relies on a combinatorial result by Kortelainen concerning word equations with iterated factors. Our result implies the decidability of the equivalence problem for the considered class of transducers. This can be seen as a first step towards proving a more general decomposition theorem for streaming string transducers with multiple registers.
Keywords
  • Streaming Transducers
  • finite valuedness
  • equivalence

Metrics

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

References

  1. R. Alur. Streaming string transducers. In Proceedings of the 18th International Workshop on Logic, Language, Information and Computation (WoLLIC), volume 6642 of LNCS, page 1, 2011. Google Scholar
  2. R. Alur and P. Cerny. Expressiveness of streaming string transducers. In Proceedings of the 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), pages 1-12, 2010. Google Scholar
  3. R. Alur and P. Cerny. Streaming transducers for algorithmic verification of single-pass list processing programs. In Proceedings of the 38th Annual ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (POPL), 2011. Google Scholar
  4. R. Alur and J. V. Deshmukh. Nondeterministic streaming state transducers. In Proceedings of the 38th International Colloquium on Automata, Languages, and Programming (ICALP), volume 6756 of LNCS, pages 1-20, 2011. Google Scholar
  5. B. Courcelle. Monadic second-order graph transductions: a survey. Theoretical Computer Science, 126:53-75, 1994. Google Scholar
  6. J. Engelfriet and H. Jan Hoogeboom. MSO definable string transductions and two-way finite-state transducers. ACM Transactions on Computational Logic, 2(2):216-254, 2001. Google Scholar
  7. J. Engelfriet and H. J. Hoogeboom. MSO-definable string transductions and two-way finite-state transducers. ACM Transactions on Computational Logic, 2(2):216-254, 2001. Google Scholar
  8. J. Engelfriet and S. Maneth. Macro Tree Transducers, Attribute Grammars, and MSO Definable Tree Translations. Infomation and Computation, 154(1):34-91, 1999. Google Scholar
  9. E. Filiot and P.-A. Reynier. On streaming string transducers and HDT0L systems. CoRR, abs/1412.0537, 2014. Google Scholar
  10. T. V. Griffiths. The unsolvability of the equivalence problem for lambda-free nondeterministic generalized machines. Journal of the ACM, 15(3):409-413, 1968. Google Scholar
  11. E. M. Gurari and O. H. Ibarra. A note on finite-valued and finitely ambiguous transducers. Mathematical Systems Theory, 16(1):61-66, 1983. Google Scholar
  12. K. Culik II and J. Karhumäki. The equivalence of finite valued transducers (on hdt0l languages) is decidable. Theoretical Computer Science, 47:71-84, 1986. Google Scholar
  13. J. Kortelainen. On the system of word equations x₀u₁^ix₁ u₂ⁱ x₂ … u_mⁱ x_m = y₀ v₁^iy₁v₂ⁱ y₂… v_mⁱ y_m (i = 0,1,2,…) in a free monoid. Journal of Automata, Languages and Combinatorics, 3(1):43-57, 1998. Google Scholar
  14. A. Saarela. Systems of word equations, polynomials and linear algebra: a new approach. European Journal of Combinatorics, 47(5):1-14, 2015. Google Scholar
  15. J. Sakarovitch and R. De Souza. On the decomposition of k-valued rational relations. In Proceedings of the 25th International Symposium on Theoretical Aspects of Computer Science (STACS), 2008. Google Scholar
  16. 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
  17. A. Weber. On the valuedness of finite transducers. Acta Informatica, 27(8):749-780, 1990. Google Scholar
  18. A. Weber. Decomposing a k-valued transducer into k unambiguous ones. Informatique théorique et applications, 30(5):379-413, 1996. 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