Document Open Access Logo

A Regular and Complete Notion of Delay for Streaming String Transducers

Authors Emmanuel Filiot , Ismaël Jecker , Christof Löding , Sarah Winter

PDF
Thumbnail PDF

File

LIPIcs.STACS.2023.32.pdf
  • Filesize: 0.83 MB
  • 16 pages

Document Identifiers

Author Details

Emmanuel Filiot
  • Université libre de Bruxelles, Belgium
Ismaël Jecker
  • University of Warsaw, Poland
Christof Löding
  • RWTH Aachen University, Germany
Sarah Winter
  • Université libre de Bruxelles, Belgium

Funding

This work was partially supported by the Fonds de la Recherche Scientifique - F.R.S.-FNRS under the MIS project F451019F.
  • Filiot, Emmanuel: Emmanuel Filiot is a senior research associate at F.R.S-FNRS.
  • Winter, Sarah: Sarah Winter is a postdoctoral researcher at F.R.S.-FNRS.

Cite As Get BibTex

Emmanuel Filiot, Ismaël Jecker, Christof Löding, and Sarah Winter. A Regular and Complete Notion of Delay for Streaming String Transducers. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 32:1-32:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.STACS.2023.32

Abstract

The notion of delay between finite transducers is a core element of numerous fundamental results of transducer theory. The goal of this work is to provide a similar notion for more complex abstract machines: we introduce a new notion of delay tailored to measure the similarity between streaming string transducers (SST). We show that our notion is regular: we design a finite automaton that can check whether the delay between any two SSTs executions is smaller than some given bound. As a consequence, our notion enjoys good decidability properties: in particular, while equivalence between non-deterministic SSTs is undecidable, we show that equivalence up to fixed delay is decidable. Moreover, we show that our notion has good completeness properties: we prove that two SSTs are equivalent if and only if they are equivalent up to some (computable) bounded delay. Together with the regularity of our delay notion, it provides an alternative proof that SSTs equivalence is decidable. Finally, the definition of our delay notion is machine-independent, as it only depends on the origin semantics of SSTs. As a corollary, the completeness result also holds for equivalent machine models such as deterministic two-way transducers, or MSO transducers.

Subject Classification

ACM Subject Classification
  • Theory of computation → Formal languages and automata theory
Keywords
  • Streaming string transducers
  • Delay
  • Origin

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 Kamal Lodaya and Meena Mahajan, editors, FSTTCS 2010, volume 8 of LIPIcs, pages 1-12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2010. URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2010.1.
  2. Rajeev Alur and Pavol Cerný. Streaming transducers for algorithmic verification of single-pass list-processing programs. In POPL 2011, pages 599-610. ACM, 2011. Google Scholar
  3. Rajeev Alur, Loris D'Antoni, and Mukund Raghothaman. Drex: A declarative language for efficiently evaluating regular string transformations. In Sriram K. Rajamani and David Walker, editors, POPL 2015, pages 125-137. ACM, 2015. URL: https://doi.org/10.1145/2676726.2676981.
  4. Rajeev Alur and Jyotirmoy V. Deshmukh. Nondeterministic streaming string transducers. In Luca Aceto, Monika Henzinger, and Jirí Sgall, editors, ICALP 2011, volume 6756 of Lecture Notes in Computer Science, pages 1-20. Springer, 2011. URL: https://doi.org/10.1007/978-3-642-22012-8_1.
  5. Rajeev Alur, Adam Freilich, and Mukund Raghothaman. Regular combinators for string transformations. In Thomas A. Henzinger and Dale Miller, editors, Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), CSL-LICS '14, Vienna, Austria, July 14-18, 2014, pages 9:1-9:10. ACM, 2014. URL: https://doi.org/10.1145/2603088.2603151.
  6. Félix Baschenis, Olivier Gauwin, Anca Muscholl, and Gabriele Puppis. Minimizing resources of sweeping and streaming string transducers. In ICALP 2016, volume 55 of LIPIcs, pages 114:1-114:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. Google Scholar
  7. Félix Baschenis, Olivier Gauwin, Anca Muscholl, and Gabriele Puppis. Untwisting two-way transducers in elementary time. In LICS 2017, pages 1-12. IEEE Computer Society, 2017. Google Scholar
  8. Nicolas Baudru and Pierre-Alain Reynier. From two-way transducers to regular function expressions. Int. J. Found. Comput. Sci., 31(6):843-873, 2020. URL: https://doi.org/10.1142/S0129054120410087.
  9. Marie-Pierre Béal, Olivier Carton, Christophe Prieur, and Jacques Sakarovitch. Squaring transducers: an efficient procedure for deciding functionality and sequentiality. Theor. Comput. Sci., 292(1):45-63, 2003. URL: https://doi.org/10.1016/S0304-3975(01)00214-6.
  10. Mikolaj Bojanczyk. Transducers with origin information. In Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, and Elias Koutsoupias, editors, ICALP 2014, volume 8573 of Lecture Notes in Computer Science, pages 26-37. Springer, 2014. URL: https://doi.org/10.1007/978-3-662-43951-7_3.
  11. Mikolaj Bojanczyk. Polyregular functions. CoRR, abs/1810.08760, 2018. URL: http://arxiv.org/abs/1810.08760.
  12. Sougata Bose. On decision problems on word transducers with origin semantics. (Sur les problèmes de décision concernant les transducteurs de mots avec la sémantique d'origine). PhD thesis, University of Bordeaux, France, 2021. URL: https://tel.archives-ouvertes.fr/tel-03216029.
  13. Sougata Bose, Anca Muscholl, Vincent Penelle, and Gabriele Puppis. Origin-equivalence of two-way word transducers is in PSPACE. CoRR, abs/1807.08053, 2018. URL: http://arxiv.org/abs/1807.08053.
  14. Christian Choffrut. Une caracterisation des fonctions sequentielles et des fonctions sous-sequentielles en tant que relations rationnelles. Theor. Comput. Sci., 5(3):325-337, 1977. URL: https://doi.org/10.1016/0304-3975(77)90049-4.
  15. Christian Choffrut. Minimizing subsequential transducers: a survey. Theor. Comput. Sci., 292(1):131-143, 2003. URL: https://doi.org/10.1016/S0304-3975(01)00219-5.
  16. Bruno Courcelle and Joost Engelfriet. Graph Structure and Monadic Second-Order Logic - A Language-Theoretic Approach, volume 138 of Encyclopedia of mathematics and its applications. Cambridge University Press, 2012. URL: http://www.cambridge.org/fr/knowledge/isbn/item5758776/?site_locale=fr_FR.
  17. Luc Dartois, Emmanuel Filiot, and Nathan Lhote. Logics for word transductions with synthesis. In Anuj Dawar and Erich Grädel, editors, Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2018, Oxford, UK, July 09-12, 2018, pages 295-304. ACM, 2018. Google Scholar
  18. Luc Dartois, Paul Gastin, R. Govind, and Shankara Narayanan Krishna. Efficient construction of reversible transducers from regular transducer expressions. In Christel Baier and Dana Fisman, editors, LICS '22: 37th Annual ACM/IEEE Symposium on Logic in Computer Science, Haifa, Israel, August 2-5, 2022, pages 50:1-50:13. ACM, 2022. Google Scholar
  19. Luc Dartois, Paul Gastin, and Shankara Narayanan Krishna. Sd-regular transducer expressions for aperiodic transformations. In 36th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2021, Rome, Italy, June 29 - July 2, 2021, pages 1-13. IEEE, 2021. URL: https://doi.org/10.1109/LICS52264.2021.9470738.
  20. Laure Daviaud, Ismaël Jecker, Pierre-Alain Reynier, and Didier Villevalois. Degree of sequentiality of weighted automata. In Javier Esparza and Andrzej S. Murawski, editors, FOSSACS 2017, volume 10203 of Lecture Notes in Computer Science, pages 215-230, 2017. URL: https://doi.org/10.1007/978-3-662-54458-7_13.
  21. Calvin C. Elgot and Jorge E. Mezei. On relations defined by generalized finite automata. IBM J. Res. Dev., 9(1):47-68, 1965. URL: https://doi.org/10.1147/rd.91.0047.
  22. Joost Engelfriet and Hendrik Jan Hoogeboom. MSO definable string transductions and two-way finite-state transducers. ACM Trans. Comput. Log., 2(2):216-254, 2001. URL: https://doi.org/10.1145/371316.371512.
  23. Emmanuel Filiot, Olivier Gauwin, Pierre-Alain Reynier, and Frédéric Servais. From two-way to one-way finite state transducers. In LICS 2013, pages 468-477. IEEE Computer Society, 2013. Google Scholar
  24. Emmanuel Filiot, Ismaël Jecker, Christof Löding, and Sarah Winter. On equivalence and uniformisation problems for finite transducers. In Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi, editors, ICALP 2016, volume 55 of LIPIcs, pages 125:1-125:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. Google Scholar
  25. Paul Gallot, Anca Muscholl, Gabriele Puppis, and Sylvain Salvati. On the decomposition of finite-valued streaming string transducers. In Heribert Vollmer and Brigitte Vallée, editors, STACS 2017, volume 66 of LIPIcs, pages 34:1-34:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.STACS.2017.34.
  26. Eitan M. Gurari. The equivalence problem for deterministic two-way sequential transducers is decidable. SIAM J. Comput., 11(3):448-452, 1982. URL: https://doi.org/10.1137/0211035.
  27. Ismaël Jecker and Emmanuel Filiot. Multi-sequential word relations. In Igor Potapov, editor, DLT 2015, volume 9168 of Lecture Notes in Computer Science, pages 288-299. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-21500-6_23.
  28. Christophe Reutenauer and Marcel Paul Schützenberger. Minimization of rational word functions. SIAM J. Comput., 20(4):669-685, 1991. URL: https://doi.org/10.1137/0220042.
  29. Jacques Sakarovitch and Rodrigo de Souza. On the decidability of bounded valuedness for transducers. In Edward Ochmanski and Jerzy Tyszkiewicz, editors, MFCS 2008, volume 5162 of Lecture Notes in Computer Science, pages 588-600. Springer, 2008. URL: https://doi.org/10.1007/978-3-540-85238-4_48.
  30. Jacques Sakarovitch and Rodrigo de Souza. On the decomposition of k-valued rational relations. In Susanne Albers and Pascal Weil, editors, STACS 2008, 25th Annual Symposium on Theoretical Aspects of Computer Science, Bordeaux, France, February 21-23, 2008, Proceedings, volume 1 of LIPIcs, pages 621-632. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Germany, 2008. URL: https://doi.org/10.4230/LIPIcs.STACS.2008.1324.
  31. Jacques Sakarovitch and Rodrigo de Souza. Lexicographic decomposition of k-valued transducers. Theory Comput. Syst., 47(3):758-785, 2010. URL: https://doi.org/10.1007/s00224-009-9206-6.
  32. Marcel Paul Schützenberger. A remark on finite transducers. Inf. Control., 4(2-3):185-196, 1961. URL: https://doi.org/10.1016/S0019-9958(61)80006-5.
  33. Andreas Weber. Decomposing A k-valued transducer into k unambiguous ones. RAIRO Theor. Informatics Appl., 30(5):379-413, 1996. URL: https://doi.org/10.1051/ita/1996300503791.
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 About DROPS Imprint Privacy Contact