LIPIcs.ICALP.2017.114.pdf
- Filesize: 8.34 MB
- 13 pages
Document
Which Classes of Origin Graphs Are Generated by Transducers
Authors
-
Part of:
Volume:
44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
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: 2017-07-07
Cite As Get BibTex
Mikolaj Bojanczyk, Laure Daviaud, Bruno Guillon, and Vincent Penelle. Which Classes of Origin Graphs Are Generated by Transducers. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 114:1-114:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.ICALP.2017.114
Abstract
We study various models of transducers equipped with origin information. We consider the semantics of these models as particular graphs, called origin graphs, and we characterise the families of such graphs recognised by streaming string transducers.
Subject Classification
Keywords
- Streaming String Transducers
- Origin Semantics
- String-to-String Transductions
- MSO Definability
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Rajeev Alur and Pavol Cerný. Expressiveness of streaming string transducers. In FSTTCS, pages 1-12, 2010. URL: http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2010.1.
- Rajeev Alur and Loris D'Antoni. Streaming tree transducers. In International Colloquium on Automata, Languages, and Programming, pages 42-53. Springer, 2012. URL: http://link.springer.com/chapter/10.1007/978-3-642-31585-5_8.
- Rajeev Alur and Jyotirmoy V. Deshmukh. Nondeterministic streaming string transducers. In International Colloquium on Automata, Languages, and Programming, pages 1-20. Springer, 2011. URL: http://link.springer.com/10.1007%2F978-3-642-22012-8_1.
-
Félix Baschenis, Olivier Gauwin, Anca Muscholl, and Gabriele Puppis. Minimizing resources of sweeping and streaming string transducers. In Proceedings of the 43rd International Colloquium on Automata, Languages and Programming (ICALP), Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016.
- Mikołaj Bojańczyk. Transducers with origin information. In Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part II, pages 26-37, 2014. URL: http://dx.doi.org/10.1007/978-3-662-43951-7_3.
- Mikołaj Bojańczyk and Michal Pilipczuk. Definability equals recognizability for graphs of bounded treewidth. In Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, LICS'16, New York, NY, USA, July 5-8, 2016, pages 407-416, 2016. URL: http://dx.doi.org/10.1145/2933575.2934508.
- J. Richard Büchi. Weak Second-Order Arithmetic and Finite Automata. Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, 6(1-6):66-92, 1960. URL: http://dx.doi.org/10.1002/malq.19600060105.
- Bruno Courcelle. The monadic second-order logic of graphs V: on closing the gap between definability and recognizability. Theor. Comput. Sci., 80(2):153-202, 1991. URL: http://dx.doi.org/10.1016/0304-3975(91)90387-H.
- 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.
- Luc Dartois, Emmanuel Filiot, and Nathan Lhote. Decidable logics for transductions and data words. CoRR, abs/1701.03670, 2017. URL: http://arxiv.org/abs/1701.03670.
- 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: http://dx.doi.org/10.1145/371316.371512.