Visibly pushdown transducers

JF Raskin, F Servais - International Colloquium on Automata, Languages …, 2008 - Springer
International Colloquium on Automata, Languages, and Programming, 2008Springer
Visibly pushdown automata have been recently introduced by Alur and Madhusudan as a
subclass of pushdown automata. This class enjoys nice properties such as closure under all
Boolean operations and the decidability of language inclusion. Along the same line, we
introduce here visibly pushdown transducers as a subclass of pushdown transducers. We
study properties of those transducers and identify subclasses with useful properties like
decidability of type checking as well as preservation of regularity of visibly pushdown …
Abstract
Visibly pushdown automata have been recently introduced by Alur and Madhusudan as a subclass of pushdown automata. This class enjoys nice properties such as closure under all Boolean operations and the decidability of language inclusion. Along the same line, we introduce here visibly pushdown transducers as a subclass of pushdown transducers. We study properties of those transducers and identify subclasses with useful properties like decidability of type checking as well as preservation of regularity of visibly pushdown languages.
Springer