Synchronization of pushdown automata

D. Caucal


Abstract

We introduce the synchronization of a pushdown automaton by a sequential transducer associating an integer to each input word. The visibly pushdown automata are the automata synchronized by an one state transducer whose output labels are -1,0,1. For each transducer, we can decide whether a pushdown automaton is synchronized. The pushdown automata synchronized by a given transducer accept languages which form an effective boolean algebra containing the regular languages and included in the deterministic real-time context-free languages.


Server START Conference Manager
Update Time 20 Feb 2006 at 20:05:03
Maintainer zdang@eecs.wsu.edu.
Start Conference Manager
Conference Systems