Document Open Access Logo

Comparison-Free Polyregular Functions

Authors Lê Thành Dũng (Tito) Nguyễn , Camille Noûs, Pierre Pradic

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2021.139.pdf
  • Filesize: 0.91 MB
  • 20 pages

Document Identifiers

Author Details

Lê Thành Dũng (Tito) Nguyễn
  • Laboratoire d'informatique de Paris Nord, Villetaneuse, France
Camille Noûs
  • Laboratoire Cogitamus, Université Volante, Sevran, France
Pierre Pradic
  • Department of Computer Science, University of Oxford, UK

Funding

  • Nguyễn, Lê Thành Dũng (Tito): Partially funded by the French ANR project CoGITARe (ANR-18-CE25-0001).

Acknowledgements

Thanks to Mikołaj Bojańczyk and Sandra Kiefer for inspiring discussions, to Gaëtan Douéneau-Tabot and Amina Doumane for explaining some features of their work to us, to Charles Paperman for his help with bibliography and to the reviewers for their feedback.

Cite AsGet BibTex

Lê Thành Dũng (Tito) Nguyễn, Camille Noûs, and Pierre Pradic. Comparison-Free Polyregular Functions. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 139:1-139:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ICALP.2021.139

Abstract

This paper introduces a new automata-theoretic class of string-to-string functions with polynomial growth. Several equivalent definitions are provided: a machine model which is a restricted variant of pebble transducers, and a few inductive definitions that close the class of regular functions under certain operations. Our motivation for studying this class comes from another characterization, which we merely mention here but prove elsewhere, based on a λ-calculus with a linear type system. As their name suggests, these comparison-free polyregular functions form a subclass of polyregular functions; we prove that the inclusion is strict. We also show that they are incomparable with HDT0L transductions, closed under usual function composition - but not under a certain "map" combinator - and satisfy a comparison-free version of the pebble minimization theorem. On the broader topic of polynomial growth transductions, we also consider the recently introduced layered streaming string transducers (SSTs), or equivalently k-marble transducers. We prove that a function can be obtained by composing such transducers together if and only if it is polyregular, and that k-layered SSTs (or k-marble transducers) are closed under "map" and equivalent to a corresponding notion of (k+1)-layered HDT0L systems.

Subject Classification

ACM Subject Classification
  • Theory of computation → Transducers
Keywords
  • pebble transducers
  • HDT0L systems
  • polyregular functions

Metrics

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

Related Versions

References

  1. Rajeev Alur and Pavol Černý. Expressiveness of streaming string transducers. In Kamal Lodaya and Meena Mahajan, editors, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2010, December 15-18, 2010, Chennai, India, 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. Michael Benedikt, Timothy Duff, Aditya Sharad, and James Worrell. Polynomial automata: Zeroness and applications. In 2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pages 1-12, Reykjavik, Iceland, June 2017. IEEE. URL: https://doi.org/10.1109/LICS.2017.8005101.
  3. Jean Berstel and Christophe Reutenauer. Noncommutative Rational Series with Applications, volume 137 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2010. Google Scholar
  4. Mikołaj Bojańczyk. Polyregular functions, 2018. URL: http://arxiv.org/abs/1810.08760.
  5. Mikołaj Bojańczyk. The Hilbert method for transducer equivalence. ACM SIGLOG News, 6(1):5-17, 2019. URL: https://doi.org/10.1145/3313909.3313911.
  6. Mikołaj Bojańczyk, Laure Daviaud, and Shankara Narayanan Krishna. Regular and First-Order List Functions. In Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science - LICS '18, pages 125-134, Oxford, United Kingdom, 2018. ACM Press. URL: https://doi.org/10.1145/3209108.3209163.
  7. Mikołaj Bojańczyk and Amina Doumane. First-order tree-to-tree functions. In Holger Hermanns, Lijun Zhang, Naoki Kobayashi, and Dale Miller, editors, LICS '20: 35th Annual ACM/IEEE Symposium on Logic in Computer Science, Saarbrücken, Germany (online conference), July 8-11, 2020, pages 252-265. ACM, 2020. URL: https://doi.org/10.1145/3373718.3394785.
  8. Mikołaj Bojańczyk, Sandra Kiefer, and Nathan Lhote. String-to-String Interpretations With Polynomial-Size Output. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 132 of Leibniz International Proceedings in Informatics (LIPIcs), pages 106:1-106:14. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.106.
  9. Michaël Cadilhac, Filip Mazowiecki, Charles Paperman, Michał Pilipczuk, and Géraud Sénizergues. On polynomial recursive sequences. In Artur Czumaj, Anuj Dawar, and Emanuela Merelli, editors, 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbrücken, Germany (Virtual Conference), volume 168 of LIPIcs, pages 117:1-117:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.ICALP.2020.117.
  10. Christian Choffrut. Sequences of words defined by two-way transducers. Theoretical Computer Science, 658:85-96, 2017. URL: https://doi.org/10.1016/j.tcs.2016.05.004.
  11. Luc Dartois, Ismaël Jecker, and Pierre-Alain Reynier. Aperiodic String Transducers. International Journal of Foundations of Computer Science, 29(05):801-824, August 2018. URL: https://doi.org/10.1142/S0129054118420054.
  12. Gaëtan Douéneau-Tabot. Pebble transducers with unary output, 2021. URL: http://arxiv.org/abs/2104.14019.
  13. Gaëtan Douéneau-Tabot, Emmanuel Filiot, and Paul Gastin. Register Transducers Are Marble Transducers. In Javier Esparza and Daniel Kráľ, editors, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020), volume 170 of Leibniz International Proceedings in Informatics (LIPIcs), pages 29:1-29:14, Dagstuhl, Germany, 2020. Schloss Dagstuhl-Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.MFCS.2020.29.
  14. Joost Engelfriet. Two-way pebble transducers for partial functions and their composition. Acta Informatica, 52(7-8):559-571, 2015. URL: https://doi.org/10.1007/s00236-015-0224-3.
  15. Joost Engelfriet and Hendrik Jan Hoogeboom. MSO definable string transductions and two-way finite-state transducers. ACM Transactions on Computational Logic, 2(2):216-254, April 2001. URL: https://doi.org/10.1145/371316.371512.
  16. Joost Engelfriet, Hendrik Jan Hoogeboom, and Bart Samwel. XML navigation and transformation by tree-walking automata and transducers with visible and invisible pebbles. Theoretical Computer Science, 850:40-97, January 2021. URL: https://doi.org/10.1016/j.tcs.2020.10.030.
  17. Joost Engelfriet and Sebastian Maneth. Two-way finite state transducers with nested pebbles. In Krzysztof Diks and Wojciech Rytter, editors, Mathematical Foundations of Computer Science 2002, 27th International Symposium, MFCS 2002, Warsaw, Poland, August 26-30, 2002, Proceedings, volume 2420 of Lecture Notes in Computer Science, pages 234-244. Springer, 2002. URL: https://doi.org/10.1007/3-540-45687-2_19.
  18. Joost Engelfriet, Grzegorz Rozenberg, and Giora Slutzki. Tree transducers, L systems, and two-way machines. Journal of Computer and System Sciences, 20(2):150-202, 1980. URL: https://doi.org/10.1016/0022-0000(80)90058-6.
  19. Joost Engelfriet and Heiko Vogler. Macro tree transducers. Journal of Computer and System Sciences, 31(1):71-146, 1985. URL: https://doi.org/10.1016/0022-0000(85)90066-2.
  20. Julien Ferté, Nathalie Marin, and Géraud Sénizergues. Word-Mappings of Level 2. Theory of Computing Systems, 54(1):111-148, January 2014. URL: https://doi.org/10.1007/s00224-013-9489-5.
  21. Emmanuel Filiot and Pierre-Alain Reynier. Transducers, Logic and Algebra for Functions of Finite Words. ACM SIGLOG News, 3(3):4-19, August 2016. URL: https://doi.org/10.1145/2984450.2984453.
  22. Emmanuel Filiot and Pierre-Alain Reynier. Copyful streaming string transducers. Fundamenta Informaticae, 178(1-2):59-76, January 2021. URL: https://doi.org/10.3233/FI-2021-1998.
  23. Bruno Guillon. Input- or output-unary sweeping transducers are weaker than their 2-way counterparts. RAIRO - Theoretical Informatics and Applications, 50(4):275-294, 2016. URL: https://doi.org/10.1051/ita/2016028.
  24. Juha Honkala. A short solution for the HDT0L sequence equivalence problem. Theoretical Computer Science, 244(1-2):267-270, 2000. URL: https://doi.org/10.1016/S0304-3975(00)00158-4.
  25. Nathan Lhote. Pebble minimization of polyregular functions. In Holger Hermanns, Lijun Zhang, Naoki Kobayashi, and Dale Miller, editors, LICS '20: 35th Annual ACM/IEEE Symposium on Logic in Computer Science, Saarbrücken, Germany, July 8-11, 2020, pages 703-712. ACM, 2020. URL: https://doi.org/10.1145/3373718.3394804.
  26. Aristid Lindenmayer. Mathematical models for cellular interactions in development II. Simple and branching filaments with two-sided inputs. Journal of Theoretical Biology, 18(3):300-315, March 1968. URL: https://doi.org/10.1016/0022-5193(68)90080-5.
  27. Damiano Mazza. Simple Parsimonious Types and Logarithmic Space. In 24th EACSL Annual Conference on Computer Science Logic (CSL 2015), pages 24-40, 2015. URL: https://doi.org/10.4230/LIPIcs.CSL.2015.24.
  28. Tova Milo, Dan Suciu, and Victor Vianu. Typechecking for XML transformers. Journal of Computer and System Sciences, 66(1):66-97, 2003. Journal version of a PODS 2000 paper. URL: https://doi.org/10.1016/S0022-0000(02)00030-2.
  29. Anca Muscholl and Gabriele Puppis. The Many Facets of String Transducers. In Rolf Niedermeier and Christophe Paul, editors, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019), volume 126 of Leibniz International Proceedings in Informatics (LIPIcs), pages 2:1-2:21. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.STACS.2019.2.
  30. Lê Thành Dũng Nguyễn, Camille Noûs, and Pierre Pradic. Implicit automata in typed λ-calculi II: streaming transducers vs categorical semantics, 2020. URL: http://arxiv.org/abs/2008.01050.
  31. Lê Thành Dũng Nguyễn and Pierre Pradic. Implicit automata in typed λ-calculi I: aperiodicity in a non-commutative logic. In Artur Czumaj, Anuj Dawar, and Emanuela Merelli, editors, 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbrücken, Germany (Virtual Conference), volume 168 of LIPIcs, pages 135:1-135:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.ICALP.2020.135.
  32. Christophe Reutenauer. Sur les séries associées à certains systèmes de Lindenmayer. Theoretical Computer Science, 9:363-375, 1979. URL: https://doi.org/10.1016/0304-3975(79)90036-7.
  33. Jacques Sakarovitch. Elements of Automata Theory. Cambridge University Press, 2009. Translated by Reuben Thomas. URL: https://doi.org/10.1017/CBO9781139195218.
  34. Janusz Schmude. On polynomial grammars extended with substitution, 2021. URL: http://arxiv.org/abs/2102.08705.
  35. Tim Smith. A pumping lemma for two-way finite transducers. In Erzsébet Csuhaj-Varjú, Martin Dietzfelbinger, and Zoltán Ésik, editors, Mathematical Foundations of Computer Science 2014 - 39th International Symposium, MFCS 2014, Budapest, Hungary, August 25-29, 2014. Proceedings, Part I, volume 8634 of Lecture Notes in Computer Science, pages 523-534. Springer, 2014. URL: https://doi.org/10.1007/978-3-662-44522-8_44.
  36. Géraud Sénizergues. Sequences of level 1, 2, 3, ..., k, ... In Volker Diekert, Mikhail V. Volkov, and Andrei Voronkov, editors, Computer Science - Theory and Applications, Second International Symposium on Computer Science in Russia, CSR 2007, Ekaterinburg, Russia, September 3-7, 2007, Proceedings, volume 4649 of Lecture Notes in Computer Science, pages 24-32. Springer, 2007. URL: https://doi.org/10.1007/978-3-540-74510-5_6.
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