A modal perspective on path constraints

被引：22

作者：

Alechina, N ^{[1
]}

Demri, S

de Rijke, M

机构：

[1] Univ Nottingham, Sch Comp Sci & IT, Nottingham NG8 1BB, England

[2] ENS Cachan, CNRS, UMR 8643, Lab Specificat & Verificat, F-94235 Cachan, France

[3] Univ Amsterdam, ILLC, Language & Inference Technol Grp, NL-1018 WV Amsterdam, Netherlands

来源：

JOURNAL OF LOGIC AND COMPUTATION | 2003年 / 13卷 / 06期

基金：

英国工程与自然科学研究理事会;

关键词：

semistructured data; path constraints; modal logic; automata theory;

D O I：

10.1093/logcom/13.6.939

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Several classes of path constraints for semistructured data are analysed and a number of decidability and complexity results proved for such constraints. While some of these decidability results were known before, it is believed that the improved complexity bounds are new. Proofs are based on techniques from modal logic and automata theory. This modal logic perspective sheds additional light on the reasons for previously known decidability and complexity results.

引用

页码：939 / 956

页数：18

共 46 条

[1] Querying documents in object databases [J].

Abiteboul S. ;

Cluet S. ;

Christophides V. ;

Milo T. ;

Moerkotte G. ;

Siméon J. .

International Journal on Digital Libraries, 1997, 1 (1) :5-19

[2] Regular path queries with constraints [J].

Abiteboul, S ;

Vianu, V .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1999, 58 (03) :428-452

[3]

ALECHINA N, 2001, 8 INT WORKSH KNOWL R

[4] Modal languages and bounded fragments of predicate logic [J].

Andreka, H ;

Nemeti, I ;

van Benthem, J .

JOURNAL OF PHILOSOPHICAL LOGIC, 1998, 27 (03) :217-274

[5]

[Anonymous], 2000, DATA WEB

[6]

Areces C, 1999, LECT NOTES COMPUT SC, V1683, P307

[7]

Balcazar J., 1988, STRUCTURAL COMPLEXIT, V1

[8] DETERMINISTIC PROPOSITIONAL DYNAMIC LOGIC - FINITE-MODELS, COMPLEXITY, AND COMPLETENESS [J].

BENARI, M ;

HALPERN, JY ;

PNUELI, A .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1982, 25 (03) :402-417

[9]

Blackburn P., 1995, Journal of Logic, Language and Information, V4, P251, DOI 10.1007/BF01049415

[10]

Buneman P., 1998, Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems. PODS 1998, P129, DOI 10.1145/275487.275502

← 1 2 3 4 5 →