Spinal-Formed Context-Free Tree Grammars
Spinal-Formed Context-Free Tree Grammars
复制标题
脊柱形成的上下文无关树语法
DOI：
--
复制
发表时间：
2000
影响因子：
0.5
通讯作者：
T. Kasai
中科院分区：
文献类型：
--
作者：
Akio Fujiyoshi;T. Kasai
抽象的。本文介绍了上下文无关树文法的一种约束模型--脊文法，并研究了它的形式性质，包括相当简单的范式。最近对自然语言的研究表明，自然语言的形式主义需要生成比上下文无关语法稍微大一点的语言类，因此树邻接语法已经被广泛研究，将它们与自然语言联系起来。证明了由脊文法生成的串语言类与树邻接文法生成的串语言类是一致的。我们还介绍了受体称为线性下推树自动机，并表明，线性下推树自动机接受正是类的树语言生成的脊椎文法。线性下推树自动机是从下推树自动机得到的，下推栈的可重复性受到限制。
Abstract. In this paper we introduce a restricted model of context-free tree grammars called spine grammars, and study their formal properties including considerably simple normal forms. Recent research on natural languages has suggested that formalisms for natural languages need to generate a slightly larger class of languages than context-free grammars, and for that reason tree adjoining grammars have been widely studied relating them to natural languages. It is shown that the class of string languages generated by spine grammars coincides with that of tree adjoining grammars. We also introduce acceptors called linear pushdown tree automata, and show that linear pushdown tree automata accept exactly the class of tree languages generated by spine grammars. Linear pushdown tree automata are obtained from pushdown tree automata with a restriction on duplicability for the pushdown stacks.