Abstract
Visibly Pushdown Transducers (VPT) form a subclass of pushdown transducers. In this paper, we investigate the extension of VPT with visibly pushdown look-ahead (VPT la ). Their transitions are guarded by visibly pushdown automata that can check whether the well-nested subword starting at the current position belongs to the language they define. First, we show that VPT la are not more expressive than VPT, but are exponentially more succinct. Second, we show that the class of deterministic VPT la corresponds exactly to the class of functional VPT, yielding a simple characterization of functional VPT. Finally, we show that while VPT la are exponentially more succinct than VPT, checking equivalence of functional VPT la is, as for VPT, ExpT-C. As a consequence, we show that any functional VPT is equivalent to an unambiguous one.
This research was supported by the projects: Gasics: “Games for Analysis and Synthesis of Interactive Computational Systems”, http://www.ulb.ac.be/di/gasics/ , and Moves: “Fundamental Issues in Modelling, Verification and Evolution of Software”, http://moves.ulb.ac.be , a PAI program funded by the Federal Belgian Government. Partially funded by the Future and Emerging Technologies (FET) programme within the Seventh Framework Programme for Research of the European Commission, under the FET-Open grant agreement FOX, No. FP7-ICT-233599.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alur, R., Madhusudan, P.: Visibly pushdown languages. In: STOC, pp. 202–211 (2004)
Alur, R., Madhusudan, P.: Adding nesting structure to words. JACM 56(3), 1–43 (2009)
Comon, H., Dauchet, M., Gilleron, R., Löding, C., Jacquemard, F., Lugiez, D., Tison, S., Tommasi, M.: Tree automata techniques and applications (2007)
Eilenberg, S.: Automata, Languages, and Machines. Academic Press, Inc. (1974)
Elgot, C.C., Mezei, J.E.: On relations defined by generalized finite automata. IBM Journal of Research and Development 9, 47–68 (1965)
Engelfriet, J.: Top-down tree transducers with regular look-ahead. Mathematical Systems Theory 10, 289–303 (1977)
Engelfriet, J.: On tree transducers for partial functions. Inf. Process. Lett. 7(4), 170–172 (1978)
Engelfriet, J., Vogler, H.: Macro tree transducers. JCSS 31(1), 71–146 (1985)
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)
Gauwin, O., Niehren, J., Tison, S.: Queries on XML streams with bounded delay and concurrency. Inf. Comput. 209(3), 409–442 (2011)
Kumar, V., Madhusudan, P., Viswanathan, M.: Visibly pushdown automata for streaming XML. In: WWW, pp. 1053–1062 (2007)
Perst, T., Seidl, H.: Macro forest transducers. IPL 89(3), 141–149 (2004)
Sakarovitch, J., de Souza, R.: Lexicographic decomposition of k-valued transducers. TCS 47(3), 758–785 (2010)
Schützenberger, M.P.: Sur les relations rationnelles entre monoides libres. TCS 3(2), 243–259 (1976)
Segoufin, L., Vianu, V.: Validating streaming XML documents. In: PODS, pp. 53–64 (2002)
Servais, F.: Visibly Pushdown Transducers. PhD thesis, Université Libre de Bruxelles (2011)
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)
Weber, A.: Decomposing finite-valued transducers and deciding their equivalence. SIAM Journal on Computing 22(1), 175–202 (1993)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Filiot, E., Servais, F. (2012). Visibly Pushdown Transducers with Look-Ahead. In: Bieliková, M., Friedrich, G., Gottlob, G., Katzenbeisser, S., Turán, G. (eds) SOFSEM 2012: Theory and Practice of Computer Science. SOFSEM 2012. Lecture Notes in Computer Science, vol 7147. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-27660-6_21
Download citation
DOI: https://doi.org/10.1007/978-3-642-27660-6_21
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-27659-0
Online ISBN: 978-3-642-27660-6
eBook Packages: Computer ScienceComputer Science (R0)