Pushdown tree automata |
| |
Authors: | Inène Guessarian |
| |
Affiliation: | (1) LITP-CNRS-UER de Mathématiques, Université Paris 7-T. 55/56, 2, Pl. Jussieu, 75251 Paris Cedex 05, France |
| |
Abstract: | We define topdown pushdown tree automata (PDTA's) which extend the usual string pushdown automata by allowing trees instead of strings in both the input and the stack. We prove that PDTA's recognize the class of context-free tree languages. (Quasi)realtime and deterministic PDTA's accept the classes of Greibach and deterministic tree languages, respectively. Finally, PDTA's are shown to be equivalent to restricted PDTA's, whose stack is linear: this both yields a more operational way of recognizing context-free tree languages and connects them with the class of indexed languages. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|