Document Open Access Logo

Register Transducers Are Marble Transducers

Authors Gaëtan Douéneau-Tabot, Emmanuel Filiot , Paul Gastin

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2020.29.pdf
  • Filesize: 0.52 MB
  • 14 pages

Document Identifiers

Author Details

Gaëtan Douéneau-Tabot
  • IRIF, Université de Paris, France
Emmanuel Filiot
  • Université libre de Bruxelles and F.R.S.-FNRS, Belgium
Paul Gastin
  • LSV, ENS Paris-Saclay, CNRS, Université Paris-Saclay, France

Funding

  • Filiot, Emmanuel: associate researcher at F.R.S.-FNRS, and supported by the MIS project F451019F (F.R.S.-FNRS).

Cite AsGet BibTex

Gaëtan Douéneau-Tabot, Emmanuel Filiot, and Paul Gastin. Register Transducers Are Marble Transducers. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 29:1-29:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.MFCS.2020.29

Abstract

Deterministic two-way transducers define the class of regular functions from words to words. Alur and Cerný introduced an equivalent model of transducers with registers called copyless streaming string transducers. In this paper, we drop the "copyless" restriction on these machines and show that they are equivalent to two-way transducers enhanced with the ability to drop marks, named "marbles", on the input. We relate the maximal number of marbles used with the amount of register copies performed by the streaming string transducer. Finally, we show that the class membership problems associated with these models are decidable. Our results can be interpreted in terms of program optimization for simple recursive and iterative programs.

Subject Classification

ACM Subject Classification
  • Theory of computation → Transducers
Keywords
  • streaming string transducer
  • two-way transducer
  • marbles
  • pebbles

Metrics

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

Related Versions

References

  1. Rajeev Alur and Pavol Cerný. Expressiveness of streaming string transducers. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2010, volume 8 of LIPIcs, pages 1-12. Schloss Dagstuhl, 2010. Google Scholar
  2. Rajeev Alur, Emmanuel Filiot, and Ashutosh Trivedi. Regular transformations of infinite strings. In Proceedings of the 27th Annual IEEE Symposium on Logic in Computer Science, LICS 2012, pages 65-74. IEEE Computer Society, 2012. Google Scholar
  3. Mikolaj Bojańczyk. Polyregular functions. arXiv preprint arXiv:1810.08760, 2018. Google Scholar
  4. Michal P Chytil and Vojtěch Jákl. Serial composition of 2-way finite-state transducers and simple programs on strings. In 4th International Colloquium on Automata, Languages, and Programming, ICALP 1977, pages 135-147. Springer, 1977. Google Scholar
  5. Luc Dartois, Paulin Fournier, Ismaël Jecker, and Nathan Lhote. On reversible transducers. In 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, volume 80 of LIPIcs, pages 113:1-113:12. Schloss Dagstuhl, 2017. Google Scholar
  6. Luc Dartois, Ismaël Jecker, and Pierre-Alain Reynier. Aperiodic string transducers. Int. J. Found. Comput. Sci., 29(5):801-824, 2018. Google Scholar
  7. Manfred Droste and Paul Gastin. Aperiodic weighted automata and weighted first-order logic. In 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019, volume 138 of LIPIcs, pages 76:1-76:15. Schloss Dagstuhl, 2019. Google Scholar
  8. Joost Engelfriet and Hendrik Jan Hoogeboom. MSO definable string transductions and two-way finite-state transducers. ACM Transactions on Computational Logic (TOCL), 2(2):216-254, 2001. Google Scholar
  9. Joost Engelfriet, Hendrik Jan Hoogeboom, and Jan-Pascal Van Best. Trips on trees. Acta Cybernetica, 14(1):51-64, 1999. Google Scholar
  10. Emmanuel Filiot and Pierre-Alain Reynier. Copyful streaming string transducers. In International Workshop on Reachability Problems, pages 75-86. Springer, 2017. Google Scholar
  11. Eitan M Gurari. The equivalence problem for deterministic two-way sequential transducers is decidable. SIAM Journal on Computing, 11(3):448-452, 1982. Google Scholar
  12. Oscar H Ibarra. Characterizations of some tape and time complexity classes of turing machines in terms of multihead and auxiliary stack automata. Journal of Computer and System Sciences, 5(2):88-117, 1971. Google Scholar
  13. Nathan Lhote. Pebble minimization of polyregular functions. In 35th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS'20, pages 703-712. ACM, 2020. Google Scholar
  14. Jacques Sakarovitch and Rodrigo De Souza. On the decidability of bounded valuedness for transducers. In International Symposium on Mathematical Foundations of Computer Science, pages 588-600. Springer, 2008. Google Scholar
  15. Dana Scott. Some definitional suggestions for automata theory. Journal of Computer and System Sciences, 1(2):187-212, 1967. Google Scholar
  16. John 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. Andreas Weber and Helmut Seidl. On the degree of ambiguity of finite automata. Theoretical Computer Science, 88(2):325-349, 1991. 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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact