|
Synchronization of pushdown automata| old_uid | 640 |
|---|
| title | Synchronization of pushdown automata |
|---|
| start_date | 2006/02/14 |
|---|
| schedule | 14h30 |
|---|
| online | no |
|---|
| summary | It is well-known that the context-free languages, or even the deterministic context-free languages, are not closed under intersection and complementation. Alur and Madhusudan have shown that the languages accepted by the visibly pushdown automata form a boolean algebra included in the deterministic real-time context-free languages.
The notion of visibly pushdown automaton is based on the synchronization between the input symbols and the actions performed on the stack: this enforces that the variation of the stack height is entirely characterized by the input word. It appears that the closure results for the languages accepted by the visibly pushdown automata are based on a geometrical property of their graphs with regard to the stack height. This geometrical property which holds for every pushdown graph (not only visibly) was encovered by Muller and Schupp.
We generalize the notion of synchronization to abstract from the stack height. To this extend, we introduce a sequential transducer associating an integer to each input word. For each transducer, we can decide whether a pushdown automaton is synchronized. For any fixed transducer, the languages accepted by the pushdown automata synchronized by this transducer, are deterministic real-time context-free languages and form an effective boolean algebra containing the regular languages. |
|---|
| responsibles | Rispal, Clément |
|---|
| |
|