ΕΛΛΕΙΠΤΙΚΗ ΣΥΜΠΕΡΑΣΜΑΤΟΛΟΓΙΑ: ΠΟΛΥΠΛΟΚΟΤΗΤΑ, ΑΛΓΟΡΙΘΜΟΙ, ΣΗΜΑΣΙΟΛΟΓΙΑ
Περίληψη
ΣΤΗΝ ΔΙΑΤΡΙΒΗ ΑΥΤΗ ΑΝΑΛΥΟΝΤΑΙ ΟΡΙΣΜΕΝΑ ΥΠΟΛΟΓΙΣΤΙΚΑ ΧΑΡΑΚΤΗΡΙΣΤΙΚΑ ΤΗΣ ΕΛΛΕΙΠΤΙΚΗΣ ΛΟΓΙΚΗΣ, ΕΝΟΣ ΑΠΟ ΤΟΥΣ ΚΥΡΙΟΤΕΡΟΥΣ ΜΗ ΜΟΝΟΤΟΝΙΚΟΥΣ ΦΟΡΜΑΛΙΣΜΟΥΣ. ΔΙΝΕΤΑΙ ΜΙΑ ΑΝΑΛΥΣΗ ΤΗΣ ΠΟΛΥΠΛΟΤΗΤΑΣ ΠΕΡΙΟΡΙΣΜΕΝΩΝ ΠΕΡΙΠΤΩΣΕΩΝ ΕΛΛΕΙΠΤΙΚΩΝ ΘΕΩΡΙΩΝ, ΜΕ ΜΕΤΑΣΧΗΜΑΤΙΣΜΟ ΤΩΝ ΘΕΩΡΙΩΝ ΣΕ ΓΡΑΦΗΜΑΤΑ. ΑΠΟ ΤΟΝ ΜΕΤΑΣΧΗΜΑΤΙΣΜΟ ΑΥΤΟ ΠΡΟΚΥΠΤΟΥΝ ΚΑΙ ΕΝΔΙΑΦΕΡΟΝΤΑ ΘΕΩΡΗΤΙΚΑ ΑΠΟΤΕΛΕΣΜΑΤΑ. ΑΚΟΛΟΥΘΩΝΤΑΣ ΤΗΝ ΓΡΑΦΟΘΕΩΡΗΤΙΚΗ ΑΥΤΗ ΠΡΟΣΕΓΓΙΣΗ ΑΝΑΠΤΥΣΟΝΤΑΙ ΔΥΟ ΑΛΓΟΡΙΘΜΟΙ ΓΙΑ ΤΗΝ ΕΥΡΕΣΗ ΠΥΡΗΝΩΝ ΣΕ ΚΑΤΕΥΘΥΝΟΜΕΝΑ ΓΡΑΦΗΜΑΤΑ. Ο ΠΡΩΤΟΣ ΕΙΝΑΙ ΑΛΓΟΡΙΘΜΟΣ ΠΟΛΥΩΝΥΜΙΚΗΣ ΚΑΘΥΣΤΕΡΗΣΗΣ ΚΑΙ ΒΡΙΣΚΕΙ ΕΝΑ ΜΕΓΑΛΟ ΥΠΟΣΥΝΟΛΟ ΤΩΝ ΠΥΡΗΝΩΝ ΓΡΑΦΗΜΑΤΟΣ ΧΩΡΙΣ ΠΕΡΙΤΤΟΥΣ ΚΥΚΛΟΥΣ. Ο ΔΕΥΤΕΡΟΣ ΛΥΝΕΙΤΟ ΠΡΟΒΛΗΜΑ ΣΤΗΝ ΓΕΝΙΚΗ ΠΕΡΙΠΤΩΣΗ. Ο ΑΛΓΟΡΙΘΜΟΣ ΑΥΤΟΣ ΧΡΗΣΙΜΟΠΟΙΕΙ ΕΝΑ ΣΥΝΟΛΟ ΚΟΡΥΦΩΝ ΑΝΑΔΡΑΣΗΣ ΓΙΑ ΤΟΝ ΠΕΡΙΟΡΙΣΜΟ ΤΩΝ ΑΠΑΙΤΟΥΜΕΝΩΝ ΥΠΟΛΟΓΙΣΜΩΝ. ΤΕΛΟΣ, ΓΙΑ ΤΟ ΔΙΚΤΥΟ ΚΛΗΡΟΝΟΜΙΚΟΤΗΤΑΣ ΑΝΑΠΤΥΣΕΤΑΙ ΜΙΑ ΣΗΜΑΣΙΟΛΟΓΙΑ ΠΟΥ ΑΠΟΤΕΛΕΙΤΑΙ ΑΠΟ ΔΥΟ ΜΕΡΗ: ΤΗΝ ΘΕΩΡΙΑ ΠΕΡΙΕΧΟΜΕΝΟΥ, ΠΟΥ ΠΕΡΙΓΡΑΦΕΙ ΤΗΝ ΓΝΩΣΗ ΓΙΑ ΤΟΝ ΚΟΣΜΟ ΚΑΙ ΤΟ ΜΟΝΤΕΛΟ ΕΠΕΞΕΡΓΑΣΙΑΣ ΠΟΥ ΕΞΗΓΕΙ ΠΩΣ ΑΥΤΗ Η ΓΝΩΣΗ ΧΡΗΣΙΜ ...
περισσότερα
Περίληψη σε άλλη γλώσσα
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)
Κατεβάστε τη διατριβή σε μορφή PDF (5.07 MB)
(Η υπηρεσία είναι διαθέσιμη μετά από δωρεάν εγγραφή)
|
Όλα τα τεκμήρια στο ΕΑΔΔ προστατεύονται από πνευματικά δικαιώματα.
|
Στατιστικά χρήσης
ΠΡΟΒΟΛΕΣ
Αφορά στις μοναδικές επισκέψεις της διδακτορικής διατριβής για την χρονική περίοδο 07/2018 - 07/2023.
Πηγή: Google Analytics.
Πηγή: Google Analytics.
ΞΕΦΥΛΛΙΣΜΑΤΑ
Αφορά στο άνοιγμα του online αναγνώστη για την χρονική περίοδο 07/2018 - 07/2023.
Πηγή: Google Analytics.
Πηγή: Google Analytics.
ΜΕΤΑΦΟΡΤΩΣΕΙΣ
Αφορά στο σύνολο των μεταφορτώσων του αρχείου της διδακτορικής διατριβής.
Πηγή: Εθνικό Αρχείο Διδακτορικών Διατριβών.
Πηγή: Εθνικό Αρχείο Διδακτορικών Διατριβών.
ΧΡΗΣΤΕΣ
Αφορά στους συνδεδεμένους στο σύστημα χρήστες οι οποίοι έχουν αλληλεπιδράσει με τη διδακτορική διατριβή. Ως επί το πλείστον, αφορά τις μεταφορτώσεις.
Πηγή: Εθνικό Αρχείο Διδακτορικών Διατριβών.
Πηγή: Εθνικό Αρχείο Διδακτορικών Διατριβών.