SOME COMPUTATIONAL ASPECTS OF CIRCUMSCRIPTION

被引：25

作者：

KOLAITIS, PG ^{[1
]}

PAPADIMITRIOU, CH ^{[1
]}

机构：

[1] UNIV CALIF SAN DIEGO,SAN DIEGO,CA 92103

来源：

JOURNAL OF THE ACM | 1990年 / 37卷 / 01期

关键词：

Circumscription; first-order logic; Horn; Model checking; nonmonotonic reasoning; NP-completeness; undecidability;

D O I：

10.1145/78935.78936

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

The effects of circumscribing first-order formulas are explored from a computational standpoint. First, extending work of V. Lifschitz, it is Shown that the circumscription of any existential first-order formula is equivalent to a first-order formula. After this, it is established that a set of universal Horn clauses has a first-order circumscription if and only if it is bounded 1990; thus it is undecidable to tell whether such formulas have first-order circumscription. Finally, it is shown that there arefirst-order formulas whode circumscription has a coNP-complete model-checking problem. © 1990, ACM. All rights reserved.

引用

页码：1 / 14

页数：14

共 32 条

[1] Aho Alfred V., 1979, 6TH P ACM S PRINC PR, P110
[2] GLOBAL INDUCTIVE DEFINABILITY
BARWISE, J
MOSCHOVAKIS, YN
[J]. JOURNAL OF SYMBOLIC LOGIC, 1978, 43 (03) : 521 - 534
[3] Barwise Jon., 1975, PERSPECTIVES MATH LO
[4] SATURATION, NONMONOTONIC REASONING AND THE CLOSED-WORLD ASSUMPTION
BOSSU, G
SIEGEL, P
[J]. ARTIFICIAL INTELLIGENCE, 1985, 25 (01) : 13 - 63
[5] STRUCTURE AND COMPLEXITY OF RELATIONAL QUERIES
CHANDRA, A
HAREL, D
[J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1982, 25 (01) : 99 - 128
[6] CHANG C. C., 1973, MODEL THEORY
[7] COSMADAKIS SS, 1988, 20TH P ACM S THEOR C, P477
[8] THE MATHEMATICS OF NON-MONOTONIC REASONING
DAVIS, M
[J]. ARTIFICIAL INTELLIGENCE, 1980, 13 (1-2) : 73 - 80
[9] Doyle J., 1985, Journal of Automated Reasoning, V1, P391, DOI 10.1007/BF00244277
[10] ETHERINGTON D, 1985, COMPUT INTELL, V1, P11

← 1 2 3 4 →