Abstract
Visibly pushdown transducers (VPTs) are visibly pushdown automata extended with outputs. They have been introduced to model transformations of nested words, i.e. words with a call/return structure. When outputs are also structured and well nested words, VPTs are a natural formalism to express tree transformations evaluated in streaming. We prove the class of VPTs with well-nested outputs to be decidable in Ptime. Moreover, we show that this class is closed under composition and that its type-checking against visibly pushdown languages is decidable.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Alur, R., Madhusudan, P.: Adding Nesting Structure to Words. Journal of the ACM 56(3), 1–43 (2009)
Bertoni, A., Choffrut, C., Radicioni, R.: The inclusion problem of context-free languages: Some tractable cases. International Journal of Foundations of Computer Science 22(2), 289–299 (2011)
von Braunmühl, B., Verbeek, R.: Input-driven Languages are Recognized in log n Space. In: Karpinski, M. (ed.) FCT 1983. LNCS, vol. 158, pp. 40–51. Springer, Heidelberg (1983)
Caralp, M., Filiot, E., Reynier, P.A., Servais, F., Talbot, J.M.: Expressiveness of visibly pushdown transducers. In: Second International Workshop on Trends in Tree Automata and Tree Transducers. EPTCS, vol. 134, pp. 17–26 (2013)
Filiot, E., Gauwin, O., Reynier, P.A., Servais, F.: Streamability of Nested Word Transductions. In: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. LIPIcs, vol. 13, pp. 312–324 (2011)
Filiot, E., Raskin, J.-F., Reynier, P.-A., Servais, F., Talbot, J.-M.: Properties of Visibly Pushdown Transducers. In: Hliněný, P., Kučera, A. (eds.) MFCS 2010. LNCS, vol. 6281, pp. 355–367. Springer, Heidelberg (2010)
Raskin, J.-F., Servais, F.: Visibly pushdown transducers. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part II. LNCS, vol. 5126, pp. 386–397. Springer, Heidelberg (2008)
Reynier, P.A., Talbot, J.M.: Visibly Pushdown Transducers with Well-nested Outputs. Tech. rep. (2014), http://hal.archives-ouvertes.fr/hal-00988129/PDF/wnVPT.pdf
Servais, F.: Visibly Pushdown Transducers. Ph.D. thesis. Université Libre de Bruxelles (2011), http://theses.ulb.ac.be/ETD-db/collection/available/ULBetd-09292011-142239/
Staworko, S., Laurence, G., Lemay, A., Niehren, J.: Equivalence of deterministic nested word to word transducers. In: Kutyłowski, M., Charatonik, W., Gębala, M. (eds.) FCT 2009. LNCS, vol. 5699, pp. 310–322. Springer, Heidelberg (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Reynier, PA., Talbot, JM. (2014). Visibly Pushdown Transducers with Well-Nested Outputs. In: Shur, A.M., Volkov, M.V. (eds) Developments in Language Theory. DLT 2014. Lecture Notes in Computer Science, vol 8633. Springer, Cham. https://doi.org/10.1007/978-3-319-09698-8_12
Download citation
DOI: https://doi.org/10.1007/978-3-319-09698-8_12
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-09697-1
Online ISBN: 978-3-319-09698-8
eBook Packages: Computer ScienceComputer Science (R0)