Expressiveness of Visibly Pushdown Transducers

Mathieu Caralp
(Aix-Marseille Université & CNRS)
Emmanuel Filiot
(Université Libre de Bruxelles)
Pierre-Alain Reynier
(Aix-Marseille Université & CNRS)
Frédéric Servais
(Hasselt University and transnational University of Limburg)
Jean-Marc Talbot
(Aix-Marseille Université & CNRS)

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. As trees and more generally hedges can be linearized into (well) nested words, VPTs are a natural formalism to express tree transformations evaluated in streaming. This paper aims at characterizing precisely the expressive power of VPTs with respect to other tree transducer models.

In Sebastian Maneth: Proceedings Second International Workshop on Trends in Tree Automata and Tree Transducers (TTATT 2013), Hanoi, Vietnam, 19/10/2013, Electronic Proceedings in Theoretical Computer Science 134, pp. 17–26.
Published: 20th November 2013.

ArXived at: bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to:
For website issues: