Boundedness of Conjunctive Regular Path Queries
Boundedness of Conjunctive Regular Path Queries
复制标题
连接正则路径查询的有界性
DOI：
10.4230/lipics.icalp.2019.104
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
M. Romero
中科院分区：
文献类型：
--
作者：
P. Barceló;Diego Figueira;M. Romero
我们研究了与倒置（UC2RPQS）结合的常规路径查询工会的界限问题。给定UC2RPQ的问题是，检查它是否等同于连接查询（UCQ）的结合。我们表明的问题是expass-complete，因此与UC2RPQ的遏制复杂性相吻合。作为推论，当UC2RPQ被界定时，它等效于最多三重指数大小的UCQ，实际上，我们表明该界限是最佳的。我们还研究了较好的UC2RPQ类，即有界厚度的无环UC2RPQ和强烈连接的UCRPQ，其界限问题分别是Pspace-Complete和$ \ pi^p_2 $ -complete。大多数上限利用距离自动机的限制结果，特别是通过交替和双向扩展模型，这可能是独立的。
We study the boundedness problem for unions of conjunctive regular path queries with inverses (UC2RPQs). This is the problem of, given a UC2RPQ, checking whether it is equivalent to a union of conjunctive queries (UCQ). We show the problem to be ExpSpace-complete, thus coinciding with the complexity of containment for UC2RPQs. As a corollary, when a UC2RPQ is bounded, it is equivalent to a UCQ of at most triple-exponential size, and in fact we show that this bound is optimal. We also study better behaved classes of UC2RPQs, namely acyclic UC2RPQs of bounded thickness, and strongly connected UCRPQs, whose boundedness problem are, respectively, PSpace-complete and $\Pi^p_2$-complete. Most upper bounds exploit results on limitedness for distance automata, in particular extending the model with alternation and two-wayness, which may be of independent interest.
可判定定点逻辑的表达能力得到提升
DOI：
10.1145/2933575.2933592
发表时间：
2016
期刊：
--
影响因子：
--
作者：
Benedikt M
通讯作者：
Benedikt M
有界问题的可判定性结果
DOI：
10.2168/lmcs-10(3:2)2014
发表时间：
2011
期刊：
Log. Methods Comput. Sci.
影响因子：
--
作者：
Achim Blumensath;Martin Otto;Mark Weyer
通讯作者：
Mark Weyer