LIPIcs.ICALP.2019.106.pdf
- Filesize: 3.35 MB
- 14 pages
Document
String-to-String Interpretations With Polynomial-Size Output (Track B: Automata, Logic, Semantics, and Theory of Programming)
Authors
-
Part of:
Volume:
46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Colloquium on Automata, Languages, and Programming (ICALP) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2019-07-04
File
Document Identifiers
Acknowledgements
The authors would like to thank Benedikt Brütsch for helpful discussions on the topic.
Cite As Get BibTex
Mikołaj Bojańczyk, Sandra Kiefer, and Nathan Lhote. String-to-String Interpretations With Polynomial-Size Output (Track B: Automata, Logic, Semantics, and Theory of Programming). In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 106:1-106:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ICALP.2019.106
Abstract
String-to-string MSO interpretations are like Courcelle’s MSO transductions, except that a single output position can be represented using a tuple of input positions instead of just a single input position. In particular, the output length is polynomial in the input length, as opposed to MSO transductions, which have output of linear length. We show that string-to-string MSO interpretations are exactly the polyregular functions. The latter class has various characterisations, one of which is that it consists of the string-to-string functions recognised by pebble transducers. Our main result implies the surprising fact that string-to-string MSO interpretations are closed under composition.
Subject Classification
ACM Subject Classification
- Theory of computation → Transducers
Keywords
- MSO
- interpretations
- pebble transducers
- polyregular functions
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Rajeev Alur and Pavol Cerný. Streaming transducers for algorithmic verification of single-pass list-processing programs. In Proceedings of the 38th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2011, Austin, TX, USA, January 26-28, 2011, pages 599-610, 2011. URL: http://dx.doi.org/10.1145/1926385.1926454.
-
Rajeev Alur, Adam Freilich, and Mukund Raghothaman. Regular combinators for string transformations. In Proceedings of the 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), page 9. ACM, 2014.
- Mikołaj Bojańczyk. Polyregular Functions, 2018. URL: http://arxiv.org/abs/1810.08760.
- Mikołaj Bojańczyk and Wojciech Czerwiński. Automata Toolbox. URL: https://www.mimuw.edu.pl/~bojan/upload/reduced-may-25.pdf.
- 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 2018, Oxford, UK, July 09-12, 2018, pages 125-134, 2018. URL: http://dx.doi.org/10.1145/3209108.3209163.
- Mikołaj Bojańczyk, Sandra Kiefer, and Nathan Lhote. String-to-string interpretations with polynomial-size output, 2019. URL: http://arxiv.org/abs/1905.13190.
-
Thomas Colcombet. A combinatorial theorem for trees. In International Colloquium on Automata, Languages, and Programming, pages 901-912. Springer, 2007.
-
Bruno Courcelle and Joost Engelfriet. Graph Structure and Monadic Second-Order Logic. A Language-Theoretic Approach. Cambridge University Press, June 2012.
- Vrunda Dave, Paul Gastin, and Shankara Narayanan Krishna. Regular Transducer Expressions for Regular Transformations. In Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2018, Oxford, UK, July 09-12, 2018, pages 315-324, 2018. URL: http://dx.doi.org/10.1145/3209108.3209182.
-
Joost Engelfriet. Two-way pebble transducers for partial functions and their composition. Acta Informatica, 52(7-8):559-571, 2015.
-
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.
-
Noa Globerman and David Harel. Complexity Results for Two-Way and Multi-Pebble Automata and their Logics. Theor. Comput. Sci., 169(2):161-184, 1996.
- Erich Grädel, Phokion G. Kolaitis, Leonid Libkin, Maarten Marx, Joel Spencer, Moshe Y. Vardi, Yde Venema, and Scott Weinstein. Finite Model Theory and Its Applications. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2007. URL: http://dx.doi.org/10.1007/3-540-68804-8.
-
Wilfrid Hodges. Model Theory. Cambridge University Press, Cambridge, March 1993.
-
Wojciech Kazana and Luc Segoufin. Enumeration of monadic second-order queries on trees. ACM Transactions on Computational Logic (TOCL), 14(4):1-12, 2013.
-
Leonid Libkin. Elements of finite model theory. Springer Science &Business Media, 2013.
-
Tova Milo, Dan Suciu, and Victor Vianu. Typechecking for XML transformers. Journal of Computer and System Sciences, 66(1):66-97, 2003.
-
Imre Simon. Factorization forests of finite height. Theoretical Computer Science, 72(1):65-94, 1990.
- Wolfgang Thomas. Languages, Automata, and Logic. In Handbook of Formal Languages, Volume 3: Beyond Words, pages 389-455. Springer, 1997. URL: http://dx.doi.org/10.1007/978-3-642-59126-6_7.