Journal Article
@Article
Artikel in Fachzeitschrift

Show entries of:

this year (2024) | last year (2023) | two years ago (2022) | Notes URL

Action:

login to update
Options:








Author, Editor(s)
Author(s):
Dimopoulos, Yannis
Magirou, Vangelis
Papadimitriou, Christos		dblp
dblp
dblp

BibTeX cite key*:

Dimopoulos-93-mpii226-2-

Title

Title*:

On Kernels, Defaults and Even Graphs

Journal

Journal Title*:

Annals of Mathematics and Artificial Intelligence
Journal's URL:


Download URL
for the article:


Language:

English

Publisher

Publisher's
Name:


Publisher's URL:


Publisher's
Address:

Saarbrücken
ISSN:


Vol, No, pp, Date

Volume*:


Number:

MPI-I-93-226

Publishing Date:

1993

Pages*:


Number of
VG Pages:


Page Start:


Page End:


Sequence Number:


DOI:


Note, Abstract, ©

Note:

To appear. Also available as Technical Report MPI-I-93-226

(LaTeX) Abstract:

Extensions in prerequisite-free, disjunction-free default theories have been shown to be in direct correspondence with kernels of directed graphs; hence default theories without odd cycles always have a ``standard'' kind of an extension. We show that, although all ``standard'' extensions can be enumerated explicitly, several other problems remain intractable for such theories: Telling whether a non-standard extension exists, enumerating all extensions, and finding the minimal standard extension. We also present a new graph-theoretic algorithm, based on vertex feedback sets, for enumerating all extensions of a general prerequisite-free, disjunction-free default theory (possibly with odd cycles). The algorithm empirically performs well for quite large theories.

URL for the Abstract:


Categories,
Keywords:


HyperLinks / References / URLs:


Copyright Message:


Personal Comments:


Download
Access Level:


Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Programming Logics Group
Audience:
experts only
Appearance:


BibTeX Entry:
@ARTICLE{Dimopoulos-93-mpii226-2-,
AUTHOR = {Dimopoulos, Yannis and Magirou, Vangelis and Papadimitriou, Christos},
 TITLE = {On Kernels, Defaults and Even Graphs},
 JOURNAL = {Annals of Mathematics and Artificial Intelligence},
 YEAR = {1993},
 TYPE = {Technical Report},
 INSTITUTION = {Max-Planck-Institut für Informatik},
 NUMBER = {MPI-I-93-226},
 ADDRESS = {Saarbr{\"u}cken},
 NOTE = {To appear. Also available as Technical Report MPI-I-93-226},
}

Entry last modified by Christine Kiesel/AG2/MPII/DE, 03/12/2010
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Uwe Brahm		Created
01/14/1995 06:51:22 PM
Revisions
7.
6.
5.
4.
3.		Editor(s)
Christine Kiesel/AG2/MPII/DE
Christine Kiesel/AG2/MPII/DE
Christine Kiesel/AG2/MPII/DE
Christine Kiesel/AG2/MPII/DE
Christine Kiesel/AG2/MPII/DE		Edit Dates
02/02/96 10:59:54
01/02/96 14:31:27
11/01/96 15:30:15
10/01/96 13:09:36
09/02/95 18:23:39