146:(it lists all editor-article relationships), and Sarah Johnson is the only editor who has not edited the article on Formal Logic. In contrast, with the open-world assumption the table is not assumed to contain all editor-article tuples, and the answer to who has not edited the Formal Logic article is unknown. There is an unknown number of editors not listed in the table, and an unknown number of articles edited by Sarah Johnson that are also not listed in the table.
1130:(PCWA). Under the PCWA, the knowledge base is generally treated under open-world semantics, yet it is possible to assert parts that should be treated under closed-world semantics, via completeness assertions. The PCWA is especially needed for situations where the CWA is not applicable due to an open domain, yet the OWA is too credulous in allowing anything to be possibly true.
77:, the closed-world assumption is used in at least two situations: (1) when the knowledge base is known to be complete (e.g., a corporate database containing records for every employee), and (2) when the knowledge base is known to be incomplete but a "best" definite answer must be derived from incomplete information. For example, if a
571:
which is inconsistent. In other words, this formalization of the closed-world assumption sometimes turns a consistent knowledge base into an inconsistent one. The closed-world assumption does not introduce an inconsistency on a knowledge base
566:
55:(OWA), stating that lack of knowledge does not imply falsity. Decisions on CWA vs. OWA determine the understanding of the actual semantics of a conceptual expression with the same notations of concepts. A successful
1377:
1123:
allows us to postulate the closed-world assumption for some statements and leave the other statements in the realm of the open-world assumption. An intermediate ground between OWA and CWA is provided by the
1111:
can be used. This regime considers knowledge bases generally to be open, i.e., potentially incomplete, yet allows to use completeness assertions to specify parts of the knowledge base that are closed.
1084:
coincide on propositional theories. The complexity of query answering (checking whether a formula is entailed by another one under the closed-world assumption) is typically in the second level of the
81:
contains the following table reporting editors who have worked on a given article, a query on the people not having edited the article on Formal Logic is usually expected to return "Sarah
Johnson".
269:
1413:
Cadoli, Marco; Lenzerini, Maurizio (April 1994). "The complexity of propositional closed world reasoning and circumscription". Journal of
Computer and System Sciences. 48 (2): 255–310.
795:
43:, is the presumption that a statement that is true is also known to be true. Therefore, conversely, what is not currently known to be true, is false. The same name also refers to a
1010:
978:
328:
378:
1048:
same as GCWA, but a positive clause is only considered if it is composed of positive literals of a given set and (both positive and negative) literals from another set;
1524:
1074:
1038:
952:
932:
905:
885:
859:
839:
819:
737:
717:
697:
677:
654:
634:
614:
590:
1277:
389:
1470:
1529:
1251:
1235:
841:
can be defined in different ways, leading to different formalizations of the closed-world assumption. The following are the definitions of
659:
Alternative formalizations not suffering from this problem have been proposed. In the following description, the considered knowledge base
1193:
Reiter, Raymond (1978). "On Closed World Data Bases". In
Gallaire, Hervé; Minker, Jack. Logic and Data Bases. Plenum Press. pp. 119–140.
1100:. Checking whether the original closed-world assumption introduces an inconsistency requires at most a logarithmic number of calls to an
56:
1304:
1549:
1198:
1519:
1107:
In situations where it is not possible to assume a closed world for all predicates, yet some of them are known to be closed, the
1144:
1108:
719:, i.e., the formulae that can be assumed to be false. In other words, the closed-world assumption applied to a knowledge base
65:
is related to the closed-world assumption, as it amounts to believing false every predicate that cannot be proved to be true.
1396:
Lifschitz, Vladimir (November 1985). "Closed-world databases and circumscription". Artificial
Intelligence. 27 (2): 229–235.
1301:
Eiter, Thomas; Gottlob, Georg (June 1993). "Propositional circumscription and extended closed-world reasoning are Î 2 p
176:
656:
having a single minimal model, where a model is minimal if no other model has a subset of variables assigned to true.
679:
is assumed to be propositional. In all cases, the formalization of the closed-world assumption is based on adding to
1544:
1219:
59:
usually cannot avoid an explicit revelation of whether the implicit logical backgrounds are based on CWA or OWA.
1554:
745:
40:
1154:
1081:
143:
1174:
1169:
1120:
983:
1443:
1139:
52:
1085:
74:
957:
1159:
1149:
277:
159:
62:
333:
36:
1520:
https://web.archive.org/web/20090624113015/http://www.betaversion.org/~stefano/linotype/news/91/
1231:
1194:
158:
consists in adding to the knowledge base the negation of the literals that are not currently
1414:
1397:
1380:
1285:
1259:
1223:
1456:
1101:
1089:
1059:
1023:
937:
917:
890:
870:
844:
824:
804:
722:
702:
682:
662:
639:
619:
599:
593:
575:
48:
1418:
1538:
1401:
1384:
1278:"Evaluation of Queries under Closed-World Assumption. Part II: The Hierarchical Case"
1164:
561:{\displaystyle \{English(Fred)\vee Irish(Fred),\neg English(Fred),\neg Irish(Fred)\}}
17:
170:, but is not guaranteed to be consistent otherwise. For example, the knowledge base
44:
1484:
1211:
1097:
167:
1289:
1263:
163:
83:
1499:
1432:
383:
Adding the negation of these two literals to the knowledge base leads to
78:
1104:; however, the exact complexity of this problem is not currently known.
1227:
1525:
Closed World
Reasoning in the Semantic Web through Epistemic Operators
1214:(1982), "On indefinite databases and the closed world assumption",
1076:
is an arbitrary formula not containing literals from a given set.
155:
1372:{\displaystyle {\displaystyle \Pi _{2}^{p}}\Pi _{2}^{p}-complete}
1093:
1530:
Excerpt from Reiter's 1978 talk on the closed world assumption
699:
the negation of the formulae that are “free for negation” for
636:; in the propositional case, this condition is equivalent to
934:
is a positive literal such that, for every positive clause
142:
In the closed-world assumption, the table is assumed to be
1498:
Razniewski, Simon; Savkovic, Ognjen; Nutt, Werner (2015).
1431:
Razniewski, Simon; Savkovic, Ognjen; Nutt, Werner (2015).
154:
The first formalization of the closed-world assumption in
1500:"Turning The Partial-closed World Assumption Upside Down"
1433:"Turning The Partial-closed World Assumption Upside Down"
861:
being free for negation in the various formalizations.
1252:"Evaluation of Queries under Closed-World Assumption."
1309:
1307:
1062:
1026:
986:
960:
940:
920:
893:
873:
847:
827:
807:
748:
725:
705:
685:
665:
642:
622:
602:
578:
392:
336:
280:
179:
51:. The opposite of the closed-world assumption is the
1218:, Lecture Notes in Computer Science, vol. 138,
1379:". Theoretical Computer Science. 114 (2): 231–245.
1371:
1068:
1032:
1004:
972:
946:
926:
899:
879:
853:
833:
813:
789:
731:
711:
691:
671:
648:
628:
608:
584:
560:
372:
322:
263:
264:{\displaystyle \{English(Fred)\vee Irish(Fred)\}}
1473:(3rd ed.). Upper Saddle River: Prentice Hall.
162:by it. The result of this addition is always
8:
784:
755:
555:
393:
258:
180:
57:formalization of natural language semantics
1471:Artificial Intelligence: A Modern Approach
1469:Russell, Stuart J.; Norvig, Peter (2010).
821:of formulae that are free for negation in
1336:
1331:
1319:
1314:
1308:
1306:
1061:
1025:
985:
959:
939:
919:
892:
872:
846:
826:
806:
790:{\displaystyle K\cup \{\neg f~|~f\in F\}}
767:
747:
724:
704:
684:
664:
641:
621:
601:
577:
391:
335:
279:
178:
1186:
1452:
1441:
1088:for general formulae, and ranges from
1040:is a conjunction of positive literals;
887:is a positive literal not entailed by
1485:"Integrity = Validity + Completeness"
1282:Kluwer Academic Publishers / Springer
1256:Kluwer Academic Publishers / Springer
1216:6th Conference on Automated Deduction
592:exactly when the intersection of all
7:
1119:The language of logic programs with
1005:{\displaystyle K\not \vdash c\vee f}
47:formalization of this assumption by
1328:
1311:
758:
519:
474:
119:Introduction to Spatial Databases
25:
1145:Partial-closed world assumption
1127:partial-closed world assumption
1115:Partial-closed world assumption
1109:partial-closed world assumption
1080:The ECWA and the formalism of
973:{\displaystyle K\not \vdash c}
768:
552:
537:
513:
498:
468:
453:
432:
417:
367:
352:
317:
302:
255:
240:
219:
204:
1:
1419:10.1016/S0022-0000(05)80004-2
865:CWA (closed-world assumption)
739:generates the knowledge base
323:{\displaystyle English(Fred)}
1402:10.1016/0004-3702(85)90055-4
1385:10.1016/0304-3975(93)90073-3
166:if the knowledge base is in
1276:Suchenek, Marek A. (2000),
1250:Suchenek, Marek A. (1997),
373:{\displaystyle Irish(Fred)}
1571:
1220:Springer Berlin Heidelberg
86:
1550:Knowledge representation
41:knowledge representation
1290:10.1023/A:1006319819647
1264:10.1023/A:1005723423016
1155:Circumscription (logic)
29:closed-world assumption
1451:Cite journal requires
1373:
1175:Unique name assumption
1170:Stable model semantics
1070:
1034:
1006:
974:
948:
928:
912:GCWA (generalized CWA)
901:
881:
855:
835:
815:
791:
733:
713:
693:
673:
650:
630:
610:
586:
562:
374:
324:
265:
150:Formalization in logic
37:formal system of logic
1374:
1140:Open-world assumption
1071:
1056:similar to CCWA, but
1035:
1017:EGCWA (extended GCWA)
1007:
975:
949:
929:
902:
882:
856:
836:
816:
792:
734:
714:
694:
674:
651:
631:
611:
587:
563:
375:
325:
266:
53:open-world assumption
18:Open world assumption
1305:
1222:, pp. 292–308,
1086:polynomial hierarchy
1060:
1024:
984:
958:
938:
918:
891:
871:
845:
825:
805:
746:
723:
703:
683:
663:
640:
620:
600:
576:
390:
334:
278:
177:
75:knowledge management
1341:
1324:
1160:Negation as failure
1150:Non-monotonic logic
1053:ECWA (extended CWA)
1020:same as above, but
616:is also a model of
63:Negation as failure
1369:
1327:
1325:
1310:
1228:10.1007/BFb0000066
1066:
1045:CCWA (careful CWA)
1030:
1002:
970:
944:
924:
897:
877:
851:
831:
811:
787:
729:
709:
689:
669:
646:
626:
606:
582:
558:
370:
320:
261:
73:In the context of
1545:Logic programming
1421:. ISSN 0022-0000.
1404:. ISSN 0004-3702.
1387:. ISSN 0304-3975.
1237:978-3-540-11558-8
1069:{\displaystyle f}
1033:{\displaystyle f}
947:{\displaystyle c}
927:{\displaystyle f}
900:{\displaystyle K}
880:{\displaystyle f}
854:{\displaystyle f}
834:{\displaystyle K}
814:{\displaystyle F}
774:
766:
732:{\displaystyle K}
712:{\displaystyle K}
692:{\displaystyle K}
672:{\displaystyle K}
649:{\displaystyle K}
629:{\displaystyle K}
609:{\displaystyle K}
585:{\displaystyle K}
139:
138:
16:(Redirected from
1562:
1507:
1506:
1504:
1495:
1489:
1488:
1480:
1474:
1467:
1461:
1460:
1454:
1449:
1447:
1439:
1437:
1428:
1422:
1411:
1405:
1394:
1388:
1378:
1376:
1375:
1370:
1340:
1335:
1326:
1323:
1318:
1299:
1293:
1292:
1273:
1267:
1266:
1247:
1241:
1240:
1208:
1202:
1191:
1129:
1128:
1075:
1073:
1072:
1067:
1039:
1037:
1036:
1031:
1011:
1009:
1008:
1003:
979:
977:
976:
971:
953:
951:
950:
945:
933:
931:
930:
925:
906:
904:
903:
898:
886:
884:
883:
878:
860:
858:
857:
852:
840:
838:
837:
832:
820:
818:
817:
812:
796:
794:
793:
788:
772:
771:
764:
738:
736:
735:
730:
718:
716:
715:
710:
698:
696:
695:
690:
678:
676:
675:
670:
655:
653:
652:
647:
635:
633:
632:
627:
615:
613:
612:
607:
591:
589:
588:
583:
567:
565:
564:
559:
379:
377:
376:
371:
329:
327:
326:
321:
274:entails neither
270:
268:
267:
262:
108:Joshua A. Norton
84:
21:
1570:
1569:
1565:
1564:
1563:
1561:
1560:
1559:
1555:Database theory
1535:
1534:
1516:
1511:
1510:
1502:
1497:
1496:
1492:
1482:
1481:
1477:
1468:
1464:
1450:
1440:
1435:
1430:
1429:
1425:
1412:
1408:
1395:
1391:
1303:
1302:
1300:
1296:
1284:(25): 247–289,
1275:
1274:
1270:
1258:(18): 237–263,
1249:
1248:
1244:
1238:
1210:
1209:
1205:
1192:
1188:
1183:
1136:
1126:
1125:
1121:strong negation
1117:
1082:circumscription
1058:
1057:
1022:
1021:
982:
981:
956:
955:
936:
935:
916:
915:
889:
888:
869:
868:
843:
842:
823:
822:
803:
802:
744:
743:
721:
720:
701:
700:
681:
680:
661:
660:
638:
637:
618:
617:
598:
597:
594:Herbrand models
574:
573:
388:
387:
332:
331:
276:
275:
175:
174:
152:
141:
71:
23:
22:
15:
12:
11:
5:
1568:
1566:
1558:
1557:
1552:
1547:
1537:
1536:
1533:
1532:
1527:
1522:
1515:
1514:External links
1512:
1509:
1508:
1490:
1483:Motro (1989).
1475:
1462:
1453:|journal=
1423:
1406:
1389:
1368:
1365:
1362:
1359:
1356:
1353:
1350:
1347:
1344:
1339:
1334:
1330:
1322:
1317:
1313:
1294:
1268:
1242:
1236:
1203:
1185:
1184:
1182:
1179:
1178:
1177:
1172:
1167:
1162:
1157:
1152:
1147:
1142:
1135:
1132:
1116:
1113:
1078:
1077:
1065:
1054:
1050:
1049:
1046:
1042:
1041:
1029:
1018:
1014:
1013:
1001:
998:
995:
992:
989:
969:
966:
963:
943:
923:
913:
909:
908:
896:
876:
866:
850:
830:
810:
799:
798:
786:
783:
780:
777:
770:
763:
760:
757:
754:
751:
728:
708:
688:
668:
645:
625:
605:
581:
569:
568:
557:
554:
551:
548:
545:
542:
539:
536:
533:
530:
527:
524:
521:
518:
515:
512:
509:
506:
503:
500:
497:
494:
491:
488:
485:
482:
479:
476:
473:
470:
467:
464:
461:
458:
455:
452:
449:
446:
443:
440:
437:
434:
431:
428:
425:
422:
419:
416:
413:
410:
407:
404:
401:
398:
395:
369:
366:
363:
360:
357:
354:
351:
348:
345:
342:
339:
319:
316:
313:
310:
307:
304:
301:
298:
295:
292:
289:
286:
283:
272:
271:
260:
257:
254:
251:
248:
245:
242:
239:
236:
233:
230:
227:
224:
221:
218:
215:
212:
209:
206:
203:
200:
197:
194:
191:
188:
185:
182:
151:
148:
137:
136:
133:
132:Emma Lee-Choon
129:
128:
125:
121:
120:
117:
113:
112:
109:
105:
104:
101:
97:
96:
93:
89:
88:
70:
67:
49:Raymond Reiter
24:
14:
13:
10:
9:
6:
4:
3:
2:
1567:
1556:
1553:
1551:
1548:
1546:
1543:
1542:
1540:
1531:
1528:
1526:
1523:
1521:
1518:
1517:
1513:
1501:
1494:
1491:
1486:
1479:
1476:
1472:
1466:
1463:
1458:
1445:
1434:
1427:
1424:
1420:
1416:
1410:
1407:
1403:
1399:
1393:
1390:
1386:
1382:
1366:
1363:
1360:
1357:
1354:
1351:
1348:
1345:
1342:
1337:
1332:
1320:
1315:
1298:
1295:
1291:
1287:
1283:
1279:
1272:
1269:
1265:
1261:
1257:
1253:
1246:
1243:
1239:
1233:
1229:
1225:
1221:
1217:
1213:
1207:
1204:
1200:
1199:9780306400605
1196:
1190:
1187:
1180:
1176:
1173:
1171:
1168:
1166:
1165:Default logic
1163:
1161:
1158:
1156:
1153:
1151:
1148:
1146:
1143:
1141:
1138:
1137:
1133:
1131:
1122:
1114:
1112:
1110:
1105:
1103:
1099:
1098:Horn formulae
1095:
1091:
1087:
1083:
1063:
1055:
1052:
1051:
1047:
1044:
1043:
1027:
1019:
1016:
1015:
999:
996:
993:
990:
987:
967:
964:
961:
941:
921:
914:
911:
910:
894:
874:
867:
864:
863:
862:
848:
828:
808:
781:
778:
775:
761:
752:
749:
742:
741:
740:
726:
706:
686:
666:
657:
643:
623:
603:
595:
579:
549:
546:
543:
540:
534:
531:
528:
525:
522:
516:
510:
507:
504:
501:
495:
492:
489:
486:
483:
480:
477:
471:
465:
462:
459:
456:
450:
447:
444:
441:
438:
435:
429:
426:
423:
420:
414:
411:
408:
405:
402:
399:
396:
386:
385:
384:
381:
364:
361:
358:
355:
349:
346:
343:
340:
337:
314:
311:
308:
305:
299:
296:
293:
290:
287:
284:
281:
252:
249:
246:
243:
237:
234:
231:
228:
225:
222:
216:
213:
210:
207:
201:
198:
195:
192:
189:
186:
183:
173:
172:
171:
169:
165:
161:
157:
149:
147:
145:
135:Formal Logic
134:
131:
130:
127:Formal Logic
126:
124:Charles Ponzi
123:
122:
118:
116:Sarah Johnson
115:
114:
111:Formal Logic
110:
107:
106:
103:Formal Logic
102:
99:
98:
94:
91:
90:
85:
82:
80:
76:
68:
66:
64:
60:
58:
54:
50:
46:
42:
38:
34:
30:
19:
1493:
1478:
1465:
1444:cite journal
1426:
1409:
1392:
1297:
1281:
1271:
1255:
1245:
1215:
1212:Minker, Jack
1206:
1189:
1118:
1106:
1079:
800:
658:
570:
382:
273:
156:formal logic
153:
140:
72:
61:
32:
28:
26:
980:, it holds
1539:Categories
1181:References
954:such that
164:consistent
1343:−
1329:Π
1312:Π
1102:NP oracle
997:∨
779:∈
759:¬
753:∪
520:¬
475:¬
436:∨
223:∨
168:Horn form
39:used for
1134:See also
991:⊬
965:⊬
801:The set
160:entailed
144:complete
100:John Doe
95:Article
79:database
35:), in a
92:Editor
69:Example
45:logical
1234:
1197:
773:
765:
1503:(PDF)
1436:(PDF)
87:Edit
1457:help
1232:ISBN
1195:ISBN
1096:for
1094:coNP
330:nor
27:The
1415:doi
1398:doi
1381:doi
1286:doi
1260:doi
1224:doi
1092:to
596:of
33:CWA
1541::
1448::
1446:}}
1442:{{
1280:,
1254:,
1230:,
380:.
1505:.
1487:.
1459:)
1455:(
1438:.
1417::
1400::
1383::
1367:e
1364:t
1361:e
1358:l
1355:p
1352:m
1349:o
1346:c
1338:p
1333:2
1321:p
1316:2
1288::
1262::
1226::
1201:.
1090:P
1064:f
1028:f
1012:;
1000:f
994:c
988:K
968:c
962:K
942:c
922:f
907:;
895:K
875:f
849:f
829:K
809:F
797:.
785:}
782:F
776:f
769:|
762:f
756:{
750:K
727:K
707:K
687:K
667:K
644:K
624:K
604:K
580:K
556:}
553:)
550:d
547:e
544:r
541:F
538:(
535:h
532:s
529:i
526:r
523:I
517:,
514:)
511:d
508:e
505:r
502:F
499:(
496:h
493:s
490:i
487:l
484:g
481:n
478:E
472:,
469:)
466:d
463:e
460:r
457:F
454:(
451:h
448:s
445:i
442:r
439:I
433:)
430:d
427:e
424:r
421:F
418:(
415:h
412:s
409:i
406:l
403:g
400:n
397:E
394:{
368:)
365:d
362:e
359:r
356:F
353:(
350:h
347:s
344:i
341:r
338:I
318:)
315:d
312:e
309:r
306:F
303:(
300:h
297:s
294:i
291:l
288:g
285:n
282:E
259:}
256:)
253:d
250:e
247:r
244:F
241:(
238:h
235:s
232:i
229:r
226:I
220:)
217:d
214:e
211:r
208:F
205:(
202:h
199:s
196:i
193:l
190:g
187:n
184:E
181:{
31:(
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.