Skip to Main content Skip to Navigation
Conference papers

Synchronization of Pushdown Automata

Didier Caucal 1
1 GALION - Graphs, Automata, Logics, Languages and vErificatiON
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, UR1 - Université de Rennes 1, INSA Rennes - Institut National des Sciences Appliquées - Rennes, CNRS - Centre National de la Recherche Scientifique : UMR6074
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.
Document type :
Conference papers
Complete list of metadatas

https://hal-upec-upem.archives-ouvertes.fr/hal-00620158
Contributor : Didier Caucal <>
Submitted on : Monday, September 30, 2013 - 7:18:03 PM
Last modification on : Friday, July 10, 2020 - 4:21:17 PM
Long-term archiving on: : Tuesday, December 31, 2013 - 2:35:13 AM

File

Sync.pdf
Files produced by the author(s)

Identifiers

Citation

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

Share

Metrics

Record views

482

Files downloads

339