302:
Körner, Philipp; Leuschel, Michael; Barbosa, JoĂŁo; Costa, VĂtor Santos; Dahl, VerĂłnica; Hermenegildo, Manuel V.; Morales, Jose F.; Wielemaker, Jan; Diaz, Daniel; Abreu, Salvador; Ciatto, Giovanni (November 2022).
184:
have a 2-valued well-founded model, in which every proposition is either true or false. This coincides with the unique stable model of the program. The well-founded semantics can be viewed as a
397:
354:
Rao, Prasad; Sagonas, Konstantinos; Swift, Terrance; Warren, David S.; Freire, Juliana (1997), Dix, JĂĽrgen; Furbach, Ulrich; Nerode, Anil (eds.),
267:
Van Gelder, Allen; Ross, Kenneth; Schlipf, John S. (1988). "Unfounded sets and well-founded semantics for general logic programs".
436:
375:
421:. Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems. ACM Press. pp. 1–10.
453:
200:
In 1989, Van Gelder suggested an algorithm to compute the well-founded semantics of a propositional logic program whose
73:
The well-founded semantics assigns a unique model to every general logic program. However, instead of only assigning
286:
42:
20:
19:
This article is about a semantics for logic programming. For the general concept in computer science, see
507:
24:
181:
402:
269:
Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on
Principles of database systems
189:
159:
8:
465:
185:
39:
416:
483:
432:
371:
336:
282:
249:
205:
46:
362:, vol. 1265, Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 430–440,
355:
475:
422:
363:
326:
316:
272:
241:
31:
201:
479:
321:
304:
501:
487:
367:
340:
253:
158:
are true or false, but both have the truth value unknown. In the two-valued
229:
277:
245:
57:
The well-founded semantics was defined by Van Gelder, et al. in 1988. The
74:
427:
331:
91:
A simple example is the logic program that encodes two propositions
470:
398:
Well-founded
Semantics Coincides with Three-Valued Stable Semantics
228:
Van Gelder, Allen; Ross, Kenneth A.; Schlipf, John S. (July 1991).
356:"XSB: A system for efficiently computing well-founded semantics"
204:
is quadratic in the size of the program. As of 2001, no general
58:
49:, which gives a precise meaning to general logic programs.
301:
62:
454:"On the problem of computing the well-founded semantics"
418:
The alternating fixpoint of logic programs with negation
271:. New York, New York, USA: ACM Press. pp. 221–230.
230:"The well-founded semantics for general logic programs"
353:
266:
227:
65:implements the well-founded semantics since 1997.
499:
451:
452:Lonc, Zbigniew; Truszczyński, Mirosław (2001).
360:Logic Programming And Nonmonotonic Reasoning
162:, there are two stable models, one in which
414:
469:
426:
330:
320:
276:
458:Theory and Practice of Logic Programming
309:Theory and Practice of Logic Programming
500:
208:algorithm for the problem was known.
68:
223:
221:
13:
305:"Fifty Years of Prolog and Beyond"
295:
14:
519:
408:
218:
16:A semantics for logic programming
445:
389:
347:
260:
1:
211:
195:
88:for representing ignorance.
21:Semantics (computer science)
7:
170:is false, and one in which
10:
524:
52:
25:Semantics (disambiguation)
18:
480:10.1017/S1471068401001053
322:10.1017/S1471068422000102
182:Stratified logic programs
368:10.1007/3-540-63255-7_33
109:
84:, it adds a third value
415:Van Gelder, A. (1989).
405:XIII pp. 445-463, 1990.
403:Fundamenta Informaticae
395:Przymusinski, Teodor.
107:is not and vice versa:
190:stable model semantics
160:stable model semantics
103:must be true whenever
36:well-founded semantics
23:. For other uses, see
278:10.1145/308386.308444
246:10.1145/116825.116838
428:10.1145/73721.73722
234:Journal of the ACM
69:Three-valued logic
508:Logic programming
438:978-0-89791-308-9
377:978-3-540-63255-9
47:logic programming
515:
492:
491:
473:
449:
443:
442:
430:
412:
406:
393:
387:
386:
385:
384:
351:
345:
344:
334:
324:
299:
293:
292:
280:
264:
258:
257:
225:
177:
173:
169:
165:
157:
153:
146:
143:
140:
137:
134:
131:
128:
125:
122:
119:
116:
113:
106:
102:
98:
94:
32:computer science
523:
522:
518:
517:
516:
514:
513:
512:
498:
497:
496:
495:
450:
446:
439:
413:
409:
394:
390:
382:
380:
378:
352:
348:
300:
296:
289:
265:
261:
226:
219:
214:
202:time complexity
198:
188:version of the
175:
171:
167:
163:
155:
151:
148:
147:
144:
141:
138:
135:
132:
129:
126:
123:
120:
117:
114:
111:
104:
100:
99:, and in which
96:
92:
71:
55:
28:
17:
12:
11:
5:
521:
511:
510:
494:
493:
464:(5): 591–609.
444:
437:
407:
388:
376:
346:
315:(6): 776–858.
294:
287:
259:
240:(3): 619–649.
216:
215:
213:
210:
197:
194:
110:
70:
67:
54:
51:
15:
9:
6:
4:
3:
2:
520:
509:
506:
505:
503:
489:
485:
481:
477:
472:
467:
463:
459:
455:
448:
440:
434:
429:
424:
420:
419:
411:
404:
400:
399:
392:
379:
373:
369:
365:
361:
357:
350:
342:
338:
333:
328:
323:
318:
314:
310:
306:
298:
290:
284:
279:
274:
270:
263:
255:
251:
247:
243:
239:
235:
231:
224:
222:
217:
209:
207:
203:
193:
191:
187:
183:
179:
161:
108:
89:
87:
83:
79:
76:
66:
64:
60:
50:
48:
44:
41:
37:
33:
26:
22:
461:
457:
447:
417:
410:
396:
391:
381:, retrieved
359:
349:
312:
308:
297:
268:
262:
237:
233:
206:subquadratic
199:
186:three-valued
180:
174:is true and
166:is true and
149:
90:
85:
81:
77:
75:propositions
72:
56:
40:three-valued
35:
29:
332:10174/33387
471:cs/0101014
383:2023-11-17
288:0897912632
212:References
196:Complexity
178:is false.
488:1471-0684
341:1471-0684
254:0004-5411
43:semantics
502:Category
150:neither
86:unknown
61:system
53:History
486:
435:
374:
339:
285:
252:
59:Prolog
34:, the
466:arXiv
82:false
38:is a
484:ISSN
433:ISBN
372:ISBN
337:ISSN
283:ISBN
250:ISSN
154:nor
95:and
78:true
45:for
476:doi
423:doi
401:.
364:doi
327:hdl
317:doi
273:doi
242:doi
136:not
118:not
80:or
63:XSB
30:In
504::
482:.
474:.
460:.
456:.
431:.
370:,
358:,
335:.
325:.
313:22
311:.
307:.
281:.
248:.
238:38
236:.
232:.
220:^
192:.
145:).
133::-
127:).
115::-
490:.
478::
468::
462:1
441:.
425::
366::
343:.
329::
319::
291:.
275::
256:.
244::
176:a
172:b
168:b
164:a
156:b
152:a
142:a
139:(
130:b
124:b
121:(
112:a
105:b
101:a
97:b
93:a
27:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.