Marrying words and trees
Marrying words and trees
复制标题
DOI：
10.1145/1265530.1265564
复制
发表时间：
2007-06
期刊：
影响因子：
--
通讯作者：
R. Alur
中科院分区：
文献类型：
--
作者：
R. Alur
传统上，既具有线性结构又具有层次结构的数据，如带注释的语言数据，使用有序树建模并使用树自动机进行查询。在本文中，我们认为嵌套词和自动机比嵌套词提供了一种更好的方法来捕捉和处理双重结构。嵌套字词泛化了字词和有序树，并允许字和树操作。我们研究了嵌套词上的各类自动机，证明了它们在表现力和简洁性方面优于词自动机和树自动机，但它们的分析复杂性和闭包性质与相应的词和树的特例类似。特别地，我们证明了有限状态嵌套字自动机可以指数级地比树自动机更简洁，下推嵌套字自动机包括上下文无关字语言和上下文无关树语言这两类不可比较的语言。
Traditionally, data that has both linear and hierarchical structure, such as annotated linguistic data, is modeled using ordered trees and queried using tree automata. In this paper, we argue that nested words and automata over nested words offer a better way to capture and process the dual structure. Nested words generalize both words and ordered trees, and allow both word and tree operations. We study various classes of automata over nested words, and show that while they enjoy expressiveness and succinctness benefits over word and tree automata, their analysis complexity and closure properties are analogous to the corresponding word and tree special cases. In particular, we show that finite-state nested word automata can be exponentially more succinct than tree automata, and pushdown nested word automata include the two incomparable classes of context-free word languages and context-free tree languages.