Visibly Pushdown Transducers

Jean-François Raskin
Friday, 15 February, 2008 (All day)

Visibly pushdown automata have been recently introduced by Alur and Madhusudan as a subclass of pushdown automata. This class enjoys nice properties like closure under all boolean operations and the decidability of language inclusion. In 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 nice properties like decidability of type checking as well as preservation of regularity of visibly pushdown languages.

Joint work with Frédéric Servais