Tree Pushdown Automata
Tree Pushdown Automata
复制标题
树下推自动机
DOI：
10.1016/0022-0000(85)90002-9
复制
发表时间：
1985
期刊：
影响因子：
--
通讯作者：
J. Gallier
中科院分区：
文献类型：
--
作者：
Karl M. Schimpf;J. Gallier
本文提出了一种新型的自动机称为树下推自动机（自下而上的树自动机与内部存储器的树的形式，类似于堆栈添加到有限状态机产生下推自动机），并表明，这种自动机识别的语言类是相同的上下文无关树语言类。
This paper presents a new type of automaton called a tree pushdown automaton (a bottom-up tree automaton augmented with internal memory in the form of a tree, similar to the way a stack is added to a finite state machine to produce a pushdown automaton) and shows that the class of languages recognized by such automata is identical to the class of context-free tree languages.