Synchronization of Pushdown Automata

Didier Caucal (1)

1 GALION - Graphs, Automata, Logics, Languages and vErificatiON

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.

Domaines: Algorithme et structure de données [cs.DS]

Didier Caucal. Synchronization of Pushdown Automata. DLT'06, Jun 2006, Santa Barbara, CA, United States. pp.120-132, ⟨10.1007/11779148_12⟩. ⟨hal-00620158⟩