文章基本信息

标题：Decidable classes of documents for XPath
本地全文：下载
作者：Vince B{\'a}r{\'a}ny ; Mikolaj Bojanczyk ; Diego Figueira 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2012
卷号：18
页码：99-111
DOI：10.4230/LIPIcs.FSTTCS.2012.99
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We study the satisfiability problem for XPath over XML documents of bounded depth. We define two parameters, called match width and braid width, that assign a number to any class of documents. We show that for all k, satisfiability for XPath restricted to bounded depth documents with match width at most k is decidable; and that XPath is undecidable on any class of documents with unbounded braid width. We conjecture that these two parameters are equivalent, in the sense that a class of documents has bounded match width iff it has bounded braid width.
关键词：XPath; XML; class automata; data trees; data words; satisfiability