Attribute grammars for unranked trees as a query language for structured documents
Attribute grammars for unranked trees as a query language for structured documents
复制标题
未排序树的属性语法作为结构化文档的查询语言
DOI：
10.1016/j.jcss.2004.10.008
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
F. Neven
中科院分区：
文献类型：
--
作者：
F. Neven
文档规范语言（例如XML）使用扩展的与上下文无关的语法来建模文档。这些语法与标准的上下文无关语法的不同之处在于，它们允许在结果的右侧使用任意正则表达式。为了查询这样的文档，我们引入了一种新形式的属性语法（扩展AGs），它直接作用于扩展的与上下文无关的语法，而不是标准的与上下文无关的语法。作为一种查询语言，扩展AGs特别相关，因为它们可以考虑文档中节点的子节点的固有顺序。我们证明了非圆在EXPTIME上是可决定的，并证明了扩展AGs的非空等价问题在EXPTIME上是完备的。作为一个应用，我们证明了区域代数表达式可以有效地转化为扩展代数表达式。这种转换极大地提高了区域代数表达式从非初等到EXPTIME的空性和等价性测试复杂度的已知上界。最后，我们用一元二阶逻辑刻画了扩展AGs的可表达性。
Document specification languages, like for instance XML, model documents using extended context-free grammars. These differ from standard context-free grammars in that they allow arbitrary regular expressions on the right-hand side of productions. To query such documents, we introduce a new form of attribute grammars (extended AGs) that work directly over extended context-free grammars rather than over standard context-free grammars. Viewed as a query language, extended AGs are particularly relevant as they can take into account the inherent order of the children of a node in a document. We show that non-circularity remains decidable in EXPTIME and establish the complexity of the non-emptiness and equivalence problem of extended AGs to be complete for EXPTIME. As an application we show that the Region Algebra expressions can be efficiently translated into extended AGs. This translation drastically improves the known upper bound on the complexity of the emptiness and equivalence test for Region Algebra expressions from non-elementary to EXPTIME. Finally, we characterize the expressiveness of extended AGs in terms of monadic second-order logic.
基于一元二阶逻辑的XML转换
DOI：
--
发表时间：
2007
期刊：
PLAN-X 2007 Informal Proceedings 1
影响因子：
--
作者：
Kazuhiro Inaba;Haruo Hosoya
通讯作者：
Haruo Hosoya
泽田浩司、中岛浩司：《今日计算机》，4. 59-64 (1987)。
DOI：
--
发表时间：
--
期刊：
影响因子：
--
作者：
通讯作者：
--