Athens University Economics and Business (AUEB)
ΕΛΛΕΙΠΤΙΚΗ ΣΥΜΠΕΡΑΣΜΑΤΟΛΟΓΙΑ: ΠΟΛΥΠΛΟΚΟΤΗΤΑ, ΑΛΓΟΡΙΘΜΟΙ, ΣΗΜΑΣΙΟΛΟΓΙΑ
Abstract
dc:descriptionTHE DEVELOPMENT OF NONMONOTONIC LOGICS AND THE ANALYSIS OF THEIR FEATURES HAS BEEN AN ESSENTIAL PART OF LOGIC RELATED RESEARCH IN ARTIFICIAL INTELLIGENCE SINCE THE EARLY 80'S. ONE OF THE PROMINENT NONMONOTONIC FORMALIZATIONS IS DEFAULT LOGIC. IN THIS THESIS WE ANALYSE SEVERAL OF ITS COMPUTATIONAL ASPECTS. WE PROVIDE AN ANALYSIS OF THE COMPLEXITY OF PROPOSITIONAL DISJUNCTION FREE DEFAULT THEORIES AND PROVE THAT EVEN IN THE CASE OF THEORIES WITHOUT PREREQUISITES, THE PROBLEM OF DETERMINING WHETHER AN EXTENSION EXISTS IS NP-COMPLETE. THIS RESULT IS OBTAINED BY TRANSFORMING PROPOSITIONAL DISJUNCTION FREE DEFAULT THEORIES TO DIRECTED GRAPHS AND PROVING THAT THE CONCEPT OF AN EXTENTION IS EQUIVALENT TO THAT OF A KERNEL IN A GRAPH. IN THIS WAY WE CREATE A CONNECTION BETWEEN DEFAULT LOGIC AND GRAPH THEORY FROM WHICH WE OBTAIN INTERESTING THEORETICAL AND COMPUTATIONAL RESULTS, WHICH ARE GENERALIZATIONS OF THE RESULTS OF KAUTZ, SELMAN AND STILLMAN. (SHORTENED)
Degree
thesis:*- Grantor dc:publisher
- Athens University Economics and Business (AUEB)
- Year dc:date
- 1992
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Δημόπουλος, Γιάννης
Subjects
dc:subject × 16- Αλγόριθμοι
- Αναπαράσταση γνώσης
- ΔΙΚΤΥΑ ΚΛΗΡΟΝΟΜΙΚΟΤΗΤΑΣ
- ΕΛΛΕΙΠΤΙΚΗ ΛΟΓΙΚΗ
- ΜΗ ΜΟΝΟΤΟΝΙΚΕΣ ΛΟΓΙΚΕΣ
- Πολυπλοκότητα
- Algorithms
- Complexity
- DEFAULT LOGIC
- INHERITANCE NETWORKS
- KNOWLEDGE REPRESENTATION ANDREASONING
- NONMONOTONIC LOGICS
- Φυσικές Επιστήμες
- Επιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική
- Natural Sciences
- Computer and Information Sciences
Rights
- Language dc:language
- gre
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/2139