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

Περίληψη

ΣΤΗΝ ΔΙΑΤΡΙΒΗ ΑΥΤΗ ΑΝΑΛΥΟΝΤΑΙ ΟΡΙΣΜΕΝΑ ΥΠΟΛΟΓΙΣΤΙΚΑ ΧΑΡΑΚΤΗΡΙΣΤΙΚΑ ΤΗΣ ΕΛΛΕΙΠΤΙΚΗΣ ΛΟΓΙΚΗΣ, ΕΝΟΣ ΑΠΟ ΤΟΥΣ ΚΥΡΙΟΤΕΡΟΥΣ ΜΗ ΜΟΝΟΤΟΝΙΚΟΥΣ ΦΟΡΜΑΛΙΣΜΟΥΣ. ΔΙΝΕΤΑΙ ΜΙΑ ΑΝΑΛΥΣΗ ΤΗΣ ΠΟΛΥΠΛΟΤΗΤΑΣ ΠΕΡΙΟΡΙΣΜΕΝΩΝ ΠΕΡΙΠΤΩΣΕΩΝ ΕΛΛΕΙΠΤΙΚΩΝ ΘΕΩΡΙΩΝ, ΜΕ ΜΕΤΑΣΧΗΜΑΤΙΣΜΟ ΤΩΝ ΘΕΩΡΙΩΝ ΣΕ ΓΡΑΦΗΜΑΤΑ. ΑΠΟ ΤΟΝ ΜΕΤΑΣΧΗΜΑΤΙΣΜΟ ΑΥΤΟ ΠΡΟΚΥΠΤΟΥΝ ΚΑΙ ΕΝΔΙΑΦΕΡΟΝΤΑ ΘΕΩΡΗΤΙΚΑ ΑΠΟΤΕΛΕΣΜΑΤΑ. ΑΚΟΛΟΥΘΩΝΤΑΣ ΤΗΝ ΓΡΑΦΟΘΕΩΡΗΤΙΚΗ ΑΥΤΗ ΠΡΟΣΕΓΓΙΣΗ ΑΝΑΠΤΥΣΟΝΤΑΙ ΔΥΟ ΑΛΓΟΡΙΘΜΟΙ ΓΙΑ ΤΗΝ ΕΥΡΕΣΗ ΠΥΡΗΝΩΝ ΣΕ ΚΑΤΕΥΘΥΝΟΜΕΝΑ ΓΡΑΦΗΜΑΤΑ. Ο ΠΡΩΤΟΣ ΕΙΝΑΙ ΑΛΓΟΡΙΘΜΟΣ ΠΟΛΥΩΝΥΜΙΚΗΣ ΚΑΘΥΣΤΕΡΗΣΗΣ ΚΑΙ ΒΡΙΣΚΕΙ ΕΝΑ ΜΕΓΑΛΟ ΥΠΟΣΥΝΟΛΟ ΤΩΝ ΠΥΡΗΝΩΝ ΓΡΑΦΗΜΑΤΟΣ ΧΩΡΙΣ ΠΕΡΙΤΤΟΥΣ ΚΥΚΛΟΥΣ. Ο ΔΕΥΤΕΡΟΣ ΛΥΝΕΙΤΟ ΠΡΟΒΛΗΜΑ ΣΤΗΝ ΓΕΝΙΚΗ ΠΕΡΙΠΤΩΣΗ. Ο ΑΛΓΟΡΙΘΜΟΣ ΑΥΤΟΣ ΧΡΗΣΙΜΟΠΟΙΕΙ ΕΝΑ ΣΥΝΟΛΟ ΚΟΡΥΦΩΝ ΑΝΑΔΡΑΣΗΣ ΓΙΑ ΤΟΝ ΠΕΡΙΟΡΙΣΜΟ ΤΩΝ ΑΠΑΙΤΟΥΜΕΝΩΝ ΥΠΟΛΟΓΙΣΜΩΝ. ΤΕΛΟΣ, ΓΙΑ ΤΟ ΔΙΚΤΥΟ ΚΛΗΡΟΝΟΜΙΚΟΤΗΤΑΣ ΑΝΑΠΤΥΣΕΤΑΙ ΜΙΑ ΣΗΜΑΣΙΟΛΟΓΙΑ ΠΟΥ ΑΠΟΤΕΛΕΙΤΑΙ ΑΠΟ ΔΥΟ ΜΕΡΗ: ΤΗΝ ΘΕΩΡΙΑ ΠΕΡΙΕΧΟΜΕΝΟΥ, ΠΟΥ ΠΕΡΙΓΡΑΦΕΙ ΤΗΝ ΓΝΩΣΗ ΓΙΑ ΤΟΝ ΚΟΣΜΟ ΚΑΙ ΤΟ ΜΟΝΤΕΛΟ ΕΠΕΞΕΡΓΑΣΙΑΣ ΠΟΥ ΕΞΗΓΕΙ ΠΩΣ ΑΥΤΗ Η ΓΝΩΣΗ ΧΡΗΣΙΜ ...
περισσότερα

Περίληψη σε άλλη γλώσσα

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)
Πρέπει να είστε εγγεγραμένος χρήστης για έχετε πρόσβαση σε όλες τις υπηρεσίες του ΕΑΔΔ  Είσοδος /Εγγραφή

Όλα τα τεκμήρια στο ΕΑΔΔ προστατεύονται από πνευματικά δικαιώματα.

DOI
10.12681/eadd/2139
Διεύθυνση Handle
http://hdl.handle.net/10442/hedi/2139
Εναλλακτικός τίτλος
DEFAULT REASONING: COMPLEXITY, ALGORITHMS, SEMANTICS
Συγγραφέας
ΔΗΜΟΠΟΥΛΟΣ, ΓΙΑΝΝΗΣ
Ημερομηνία
1992
Ίδρυμα
Οικονομικό Πανεπιστήμιο Αθηνών. Τμήμα Εφαρμοσμένης Πληροφορικής
Εξεταστική επιτροπή
ΜΑΓΕΙΡΟΥ ΕΥΑΓΓΕΛΟΣ
ΚΑΒΟΥΡΑΣ ΙΩΑΝΝΗΣ
ΚΟΝΤΟΣ ΙΩΑΝΝΗΣ
ΠΡΩΤΟΝΟΤΑΡΙΟΣ ΕΜΜΑΝΟΥΗΛ
ΖΑΧΟΣ ΕΥΣΤΑΘΙΟΣ
Επιστημονικό πεδίο
Φυσικές Επιστήμες
Επιστήμες Ηλεκτρονικών Υπολογιστών & Πληροφορικής
Λέξεις-κλειδιά
Αλγόριθμοι; Αναπαράσταση γνώσης; ΔΙΚΤΥΑ ΚΛΗΡΟΝΟΜΙΚΟΤΗΤΑΣ; ΕΛΛΕΙΠΤΙΚΗ ΛΟΓΙΚΗ; ΜΗ ΜΟΝΟΤΟΝΙΚΕΣ ΛΟΓΙΚΕΣ; Πολυπλοκότητα
Χώρα
Ελλάδα
Γλώσσα
Ελληνικά