Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | 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