A polynomial translation from the two-variable guarded fragment with number restrictions to the guarded fragment

被引：13

作者：

Kazakov, Y ^{[1
]}

机构：

[1] MPI Informat, D-66123 Saarbrucken, Germany

来源：

LOGICS IN ARTIFICIAL INTELLIGENCE, PROCEEDINGS | 2004年 / 3229卷

关键词：

D O I：

10.1007/978-3-540-30227-8_32

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

We consider a two-variable guarded fragment with number restrictions for binary relations and give a satisfiability preserving transformation of formulas in this fragment to the three-variable guarded fragment. The translation can be computed in polynomial time and produces a formula that is linear in the size of the initial formula even for the binary coding of number restrictions. This allows one to reduce reasoning problems for many description logics to the satisfiability problem for the guarded fragment.

引用

页码：372 / 384

页数：13

共 10 条

[1] Modal languages and bounded fragments of predicate logic
Andreka, H
Nemeti, I
van Benthem, J
[J]. JOURNAL OF PHILOSOPHICAL LOGIC, 1998, 27 (03) : 217 - 274
[2] Ganzinger H., 1999, Proceedings. 14th Symposium on Logic in Computer Science (Cat. No. PR00158), P295, DOI 10.1109/LICS.1999.782624
[3] On the restraining power of guards
Grädel, E
[J]. JOURNAL OF SYMBOLIC LOGIC, 1999, 64 (04) : 1719 - 1742
[4] Gradel E., 1999, LNCS, V1632
[5] HAARSLEV V, 2001, P INT WORKSH METH MO, V2
[6] HARASLEV V, 2001, P INT WORKSH DESCR L, P142
[7] HLADIK J, 2002, LECT NOTES ARTIFICIA, V2381
[8] HLADIK J, 2003, LECT NOTES ARTIFICIA, V2741
[9] TOBIES S, 2001, THESIS RWTH AACHEN G
[10] Vardi Moshe Y., 1996, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, V31, P149, DOI 10.1090/

← 1 →