ΕΛΛΕΙΠΤΙΚΗ ΣΥΜΠΕΡΑΣΜΑΤΟΛΟΓΙΑ: ΠΟΛΥΠΛΟΚΟΤΗΤΑ, ΑΛΓΟΡΙΘΜΟΙ, ΣΗΜΑΣΙΟΛΟΓΙΑ

Abstract

THE 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)

ΣΤΗΝ ΔΙΑΤΡΙΒΗ ΑΥΤΗ ΑΝΑΛΥΟΝΤΑΙ ΟΡΙΣΜΕΝΑ ΥΠΟΛΟΓΙΣΤΙΚΑ ΧΑΡΑΚΤΗΡΙΣΤΙΚΑ ΤΗΣ ΕΛΛΕΙΠΤΙΚΗΣ ΛΟΓΙΚΗΣ, ΕΝΟΣ ΑΠΟ ΤΟΥΣ ΚΥΡΙΟΤΕΡΟΥΣ ΜΗ ΜΟΝΟΤΟΝΙΚΟΥΣ ΦΟΡΜΑΛΙΣΜΟΥΣ. ΔΙΝΕΤΑΙ ΜΙΑ ΑΝΑΛΥΣΗ ΤΗΣ ΠΟΛΥΠΛΟΤΗΤΑΣ ΠΕΡΙΟΡΙΣΜΕΝΩΝ ΠΕΡΙΠΤΩΣΕΩΝ ΕΛΛΕΙΠΤΙΚΩΝ ΘΕΩΡΙΩΝ, ΜΕ ΜΕΤΑΣΧΗΜΑΤΙΣΜΟ ΤΩΝ ΘΕΩΡΙΩΝ ΣΕ ΓΡΑΦΗΜΑΤΑ. ΑΠΟ ΤΟΝ ΜΕΤΑΣΧΗΜΑΤΙΣΜΟ ΑΥΤΟ ΠΡΟΚΥΠΤΟΥΝ ΚΑΙ ΕΝΔΙΑΦΕΡΟΝΤΑ ΘΕΩΡΗΤΙΚΑ ΑΠΟΤΕΛΕΣΜΑΤΑ. ΑΚΟΛΟΥΘΩΝΤΑΣ ΤΗΝ ΓΡΑΦΟΘΕΩΡΗΤΙΚΗ ΑΥΤΗ ΠΡΟΣΕΓΓΙΣΗ ΑΝΑΠΤΥΣΟΝΤΑΙ ΔΥΟ ΑΛΓΟΡΙΘΜΟΙ ΓΙΑ ΤΗΝ ΕΥΡΕΣΗ ΠΥΡΗΝΩΝ ΣΕ ΚΑΤΕΥΘΥΝΟΜΕΝΑ ΓΡΑΦΗΜΑΤΑ. Ο ΠΡΩΤΟΣ ΕΙΝΑΙ ΑΛΓΟΡΙΘΜΟΣ ΠΟΛΥΩΝΥΜΙΚΗΣ ΚΑΘΥΣΤΕΡΗΣΗΣ ΚΑΙ ΒΡΙΣΚΕΙ ΕΝΑ ΜΕΓΑΛΟ ΥΠΟΣΥΝΟΛΟ ΤΩΝ ΠΥΡΗΝΩΝ ΓΡΑΦΗΜΑΤΟΣ ΧΩΡΙΣ ΠΕΡΙΤΤΟΥΣ ΚΥΚΛΟΥΣ. Ο ΔΕΥΤΕΡΟΣ ΛΥΝΕΙΤΟ ΠΡΟΒΛΗΜΑ ΣΤΗΝ ΓΕΝΙΚΗ ΠΕΡΙΠΤΩΣΗ. Ο ΑΛΓΟΡΙΘΜΟΣ ΑΥΤΟΣ ΧΡΗΣΙΜΟΠΟΙΕΙ ΕΝΑ ΣΥΝΟΛΟ ΚΟΡΥΦΩΝ ΑΝΑΔΡΑΣΗΣ ΓΙΑ ΤΟΝ ΠΕΡΙΟΡΙΣΜΟ ΤΩΝ ΑΠΑΙΤΟΥΜΕΝΩΝ ΥΠΟΛΟΓΙΣΜΩΝ. ΤΕΛΟΣ, ΓΙΑ ΤΟ ΔΙΚΤΥΟ ΚΛΗΡΟΝΟΜΙΚΟΤΗΤΑΣ ΑΝΑΠΤΥΣΕΤΑΙ ΜΙΑ ΣΗΜΑΣΙΟΛΟΓΙΑ ΠΟΥ ΑΠΟΤΕΛΕΙΤΑΙ ΑΠΟ ΔΥΟ ΜΕΡΗ: ΤΗΝ ΘΕΩΡΙΑ ΠΕΡΙΕΧΟΜΕΝΟΥ, ΠΟΥ ΠΕΡΙΓΡΑΦΕΙ ΤΗΝ ΓΝΩΣΗ ΓΙΑ ΤΟΝ ΚΟΣΜΟ ΚΑΙ ΤΟ ΜΟΝΤΕΛΟ ΕΠΕΞΕΡΓΑΣΙΑΣ ΠΟΥ ΕΞΗΓΕΙ ΠΩΣ ΑΥΤΗ Η ΓΝΩΣΗ ΧΡΗΣΙΜΟΠΟΙΕΙΤΑΙ.