{"id":{"repo_id":"greece","oai_identifier":"oai:10442/2139"},"canonical_url":"https://search.ndltd.org/etd/greece/oai:10442/2139","repository":{"repo_id":"greece","name":"Greek National Archive of PhD Theses","base_url":"https://phdtheses.ekt.gr/eadd_oai/request"},"display":{"title":"ΕΛΛΕΙΠΤΙΚΗ ΣΥΜΠΕΡΑΣΜΑΤΟΛΟΓΙΑ: ΠΟΛΥΠΛΟΚΟΤΗΤΑ, ΑΛΓΟΡΙΘΜΟΙ, ΣΗΜΑΣΙΟΛΟΓΙΑ","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)","abstract_html":"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&#x27;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)","abstract_has_math":false,"creators":["Δημόπουλος, Γιάννης"],"institution":"Athens University Economics and Business (AUEB)","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":1992,"date_issued":"1992","date_published":"1992","updated_at":"2026-11-18T20:21:24Z","subjects":["Αλγόριθμοι","Αναπαράσταση γνώσης","ΔΙΚΤΥΑ ΚΛΗΡΟΝΟΜΙΚΟΤΗΤΑΣ","ΕΛΛΕΙΠΤΙΚΗ ΛΟΓΙΚΗ","ΜΗ ΜΟΝΟΤΟΝΙΚΕΣ ΛΟΓΙΚΕΣ","Πολυπλοκότητα","Algorithms","Complexity","DEFAULT LOGIC","INHERITANCE NETWORKS","KNOWLEDGE REPRESENTATION ANDREASONING","NONMONOTONIC LOGICS","Φυσικές Επιστήμες","Επιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική","Natural Sciences","Computer and Information Sciences"],"languages":["gre"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["10.12681/eadd/2139"],"render_values":[{"text":"10.12681/eadd/2139","href":"https://doi.org/10.12681/eadd/2139","code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/10442/hedi/2139","outbound_label":"Handle","outbound_source":"dc:identifier","record_url":"http://hdl.handle.net/10442/hedi/2139","record_label":"Repository record","record_kind":"handle","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://phdtheses.ekt.gr/eadd_oai/request?verb=GetRecord&metadataPrefix=oai_dc&identifier=oai%3A10442%2F2139","prefix":"oai_dc"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Δημόπουλος, Γιάννης"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["1992"]},{"key":"dc:publisher","label":"Institution","values":["Athens University Economics and Business (AUEB)","Οικονομικό Πανεπιστήμιο Αθηνών"]},{"key":"dc:type","label":"Dc Type","values":["PhD Thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Αλγόριθμοι","Αναπαράσταση γνώσης","ΔΙΚΤΥΑ ΚΛΗΡΟΝΟΜΙΚΟΤΗΤΑΣ","ΕΛΛΕΙΠΤΙΚΗ ΛΟΓΙΚΗ","ΜΗ ΜΟΝΟΤΟΝΙΚΕΣ ΛΟΓΙΚΕΣ","Πολυπλοκότητα","Algorithms","Complexity","DEFAULT LOGIC","INHERITANCE NETWORKS","KNOWLEDGE REPRESENTATION ANDREASONING","NONMONOTONIC LOGICS","Φυσικές Επιστήμες","Επιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική","Natural Sciences","Computer and Information Sciences"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["gre"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["10.12681/eadd/2139","http://hdl.handle.net/10442/hedi/2139"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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)","ΣΤΗΝ ΔΙΑΤΡΙΒΗ ΑΥΤΗ ΑΝΑΛΥΟΝΤΑΙ ΟΡΙΣΜΕΝΑ ΥΠΟΛΟΓΙΣΤΙΚΑ ΧΑΡΑΚΤΗΡΙΣΤΙΚΑ ΤΗΣ ΕΛΛΕΙΠΤΙΚΗΣ ΛΟΓΙΚΗΣ, ΕΝΟΣ ΑΠΟ ΤΟΥΣ ΚΥΡΙΟΤΕΡΟΥΣ ΜΗ ΜΟΝΟΤΟΝΙΚΟΥΣ ΦΟΡΜΑΛΙΣΜΟΥΣ. ΔΙΝΕΤΑΙ ΜΙΑ ΑΝΑΛΥΣΗ ΤΗΣ ΠΟΛΥΠΛΟΤΗΤΑΣ ΠΕΡΙΟΡΙΣΜΕΝΩΝ ΠΕΡΙΠΤΩΣΕΩΝ ΕΛΛΕΙΠΤΙΚΩΝ ΘΕΩΡΙΩΝ, ΜΕ ΜΕΤΑΣΧΗΜΑΤΙΣΜΟ ΤΩΝ ΘΕΩΡΙΩΝ ΣΕ ΓΡΑΦΗΜΑΤΑ. ΑΠΟ ΤΟΝ ΜΕΤΑΣΧΗΜΑΤΙΣΜΟ ΑΥΤΟ ΠΡΟΚΥΠΤΟΥΝ ΚΑΙ ΕΝΔΙΑΦΕΡΟΝΤΑ ΘΕΩΡΗΤΙΚΑ ΑΠΟΤΕΛΕΣΜΑΤΑ. ΑΚΟΛΟΥΘΩΝΤΑΣ ΤΗΝ ΓΡΑΦΟΘΕΩΡΗΤΙΚΗ ΑΥΤΗ ΠΡΟΣΕΓΓΙΣΗ ΑΝΑΠΤΥΣΟΝΤΑΙ ΔΥΟ ΑΛΓΟΡΙΘΜΟΙ ΓΙΑ ΤΗΝ ΕΥΡΕΣΗ ΠΥΡΗΝΩΝ ΣΕ ΚΑΤΕΥΘΥΝΟΜΕΝΑ ΓΡΑΦΗΜΑΤΑ. Ο ΠΡΩΤΟΣ ΕΙΝΑΙ ΑΛΓΟΡΙΘΜΟΣ ΠΟΛΥΩΝΥΜΙΚΗΣ ΚΑΘΥΣΤΕΡΗΣΗΣ ΚΑΙ ΒΡΙΣΚΕΙ ΕΝΑ ΜΕΓΑΛΟ ΥΠΟΣΥΝΟΛΟ ΤΩΝ ΠΥΡΗΝΩΝ ΓΡΑΦΗΜΑΤΟΣ ΧΩΡΙΣ ΠΕΡΙΤΤΟΥΣ ΚΥΚΛΟΥΣ. Ο ΔΕΥΤΕΡΟΣ ΛΥΝΕΙΤΟ ΠΡΟΒΛΗΜΑ ΣΤΗΝ ΓΕΝΙΚΗ ΠΕΡΙΠΤΩΣΗ. Ο ΑΛΓΟΡΙΘΜΟΣ ΑΥΤΟΣ ΧΡΗΣΙΜΟΠΟΙΕΙ ΕΝΑ ΣΥΝΟΛΟ ΚΟΡΥΦΩΝ ΑΝΑΔΡΑΣΗΣ ΓΙΑ ΤΟΝ ΠΕΡΙΟΡΙΣΜΟ ΤΩΝ ΑΠΑΙΤΟΥΜΕΝΩΝ ΥΠΟΛΟΓΙΣΜΩΝ. ΤΕΛΟΣ, ΓΙΑ ΤΟ ΔΙΚΤΥΟ ΚΛΗΡΟΝΟΜΙΚΟΤΗΤΑΣ ΑΝΑΠΤΥΣΕΤΑΙ ΜΙΑ ΣΗΜΑΣΙΟΛΟΓΙΑ ΠΟΥ ΑΠΟΤΕΛΕΙΤΑΙ ΑΠΟ ΔΥΟ ΜΕΡΗ: ΤΗΝ ΘΕΩΡΙΑ ΠΕΡΙΕΧΟΜΕΝΟΥ, ΠΟΥ ΠΕΡΙΓΡΑΦΕΙ ΤΗΝ ΓΝΩΣΗ ΓΙΑ ΤΟΝ ΚΟΣΜΟ ΚΑΙ ΤΟ ΜΟΝΤΕΛΟ ΕΠΕΞΕΡΓΑΣΙΑΣ ΠΟΥ ΕΞΗΓΕΙ ΠΩΣ ΑΥΤΗ Η ΓΝΩΣΗ ΧΡΗΣΙΜΟΠΟΙΕΙΤΑΙ."]},{"key":"dc:title","label":"Title","values":["ΕΛΛΕΙΠΤΙΚΗ ΣΥΜΠΕΡΑΣΜΑΤΟΛΟΓΙΑ: ΠΟΛΥΠΛΟΚΟΤΗΤΑ, ΑΛΓΟΡΙΘΜΟΙ, ΣΗΜΑΣΙΟΛΟΓΙΑ","DEFAULT REASONING: COMPLEXITY, ALGORITHMS, SEMANTICS"]}]}],"canonical_facts":{"dc:creator":["Δημόπουλος, Γιάννης"],"dc:date":["1992"],"dc:description":["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)","ΣΤΗΝ ΔΙΑΤΡΙΒΗ ΑΥΤΗ ΑΝΑΛΥΟΝΤΑΙ ΟΡΙΣΜΕΝΑ ΥΠΟΛΟΓΙΣΤΙΚΑ ΧΑΡΑΚΤΗΡΙΣΤΙΚΑ ΤΗΣ ΕΛΛΕΙΠΤΙΚΗΣ ΛΟΓΙΚΗΣ, ΕΝΟΣ ΑΠΟ ΤΟΥΣ ΚΥΡΙΟΤΕΡΟΥΣ ΜΗ ΜΟΝΟΤΟΝΙΚΟΥΣ ΦΟΡΜΑΛΙΣΜΟΥΣ. ΔΙΝΕΤΑΙ ΜΙΑ ΑΝΑΛΥΣΗ ΤΗΣ ΠΟΛΥΠΛΟΤΗΤΑΣ ΠΕΡΙΟΡΙΣΜΕΝΩΝ ΠΕΡΙΠΤΩΣΕΩΝ ΕΛΛΕΙΠΤΙΚΩΝ ΘΕΩΡΙΩΝ, ΜΕ ΜΕΤΑΣΧΗΜΑΤΙΣΜΟ ΤΩΝ ΘΕΩΡΙΩΝ ΣΕ ΓΡΑΦΗΜΑΤΑ. ΑΠΟ ΤΟΝ ΜΕΤΑΣΧΗΜΑΤΙΣΜΟ ΑΥΤΟ ΠΡΟΚΥΠΤΟΥΝ ΚΑΙ ΕΝΔΙΑΦΕΡΟΝΤΑ ΘΕΩΡΗΤΙΚΑ ΑΠΟΤΕΛΕΣΜΑΤΑ. ΑΚΟΛΟΥΘΩΝΤΑΣ ΤΗΝ ΓΡΑΦΟΘΕΩΡΗΤΙΚΗ ΑΥΤΗ ΠΡΟΣΕΓΓΙΣΗ ΑΝΑΠΤΥΣΟΝΤΑΙ ΔΥΟ ΑΛΓΟΡΙΘΜΟΙ ΓΙΑ ΤΗΝ ΕΥΡΕΣΗ ΠΥΡΗΝΩΝ ΣΕ ΚΑΤΕΥΘΥΝΟΜΕΝΑ ΓΡΑΦΗΜΑΤΑ. Ο ΠΡΩΤΟΣ ΕΙΝΑΙ ΑΛΓΟΡΙΘΜΟΣ ΠΟΛΥΩΝΥΜΙΚΗΣ ΚΑΘΥΣΤΕΡΗΣΗΣ ΚΑΙ ΒΡΙΣΚΕΙ ΕΝΑ ΜΕΓΑΛΟ ΥΠΟΣΥΝΟΛΟ ΤΩΝ ΠΥΡΗΝΩΝ ΓΡΑΦΗΜΑΤΟΣ ΧΩΡΙΣ ΠΕΡΙΤΤΟΥΣ ΚΥΚΛΟΥΣ. Ο ΔΕΥΤΕΡΟΣ ΛΥΝΕΙΤΟ ΠΡΟΒΛΗΜΑ ΣΤΗΝ ΓΕΝΙΚΗ ΠΕΡΙΠΤΩΣΗ. Ο ΑΛΓΟΡΙΘΜΟΣ ΑΥΤΟΣ ΧΡΗΣΙΜΟΠΟΙΕΙ ΕΝΑ ΣΥΝΟΛΟ ΚΟΡΥΦΩΝ ΑΝΑΔΡΑΣΗΣ ΓΙΑ ΤΟΝ ΠΕΡΙΟΡΙΣΜΟ ΤΩΝ ΑΠΑΙΤΟΥΜΕΝΩΝ ΥΠΟΛΟΓΙΣΜΩΝ. ΤΕΛΟΣ, ΓΙΑ ΤΟ ΔΙΚΤΥΟ ΚΛΗΡΟΝΟΜΙΚΟΤΗΤΑΣ ΑΝΑΠΤΥΣΕΤΑΙ ΜΙΑ ΣΗΜΑΣΙΟΛΟΓΙΑ ΠΟΥ ΑΠΟΤΕΛΕΙΤΑΙ ΑΠΟ ΔΥΟ ΜΕΡΗ: ΤΗΝ ΘΕΩΡΙΑ ΠΕΡΙΕΧΟΜΕΝΟΥ, ΠΟΥ ΠΕΡΙΓΡΑΦΕΙ ΤΗΝ ΓΝΩΣΗ ΓΙΑ ΤΟΝ ΚΟΣΜΟ ΚΑΙ ΤΟ ΜΟΝΤΕΛΟ ΕΠΕΞΕΡΓΑΣΙΑΣ ΠΟΥ ΕΞΗΓΕΙ ΠΩΣ ΑΥΤΗ Η ΓΝΩΣΗ ΧΡΗΣΙΜΟΠΟΙΕΙΤΑΙ."],"dc:identifier":["10.12681/eadd/2139","http://hdl.handle.net/10442/hedi/2139"],"dc:language":["gre"],"dc:publisher":["Athens University Economics and Business (AUEB)","Οικονομικό Πανεπιστήμιο Αθηνών"],"dc:subject":["Αλγόριθμοι","Αναπαράσταση γνώσης","ΔΙΚΤΥΑ ΚΛΗΡΟΝΟΜΙΚΟΤΗΤΑΣ","ΕΛΛΕΙΠΤΙΚΗ ΛΟΓΙΚΗ","ΜΗ ΜΟΝΟΤΟΝΙΚΕΣ ΛΟΓΙΚΕΣ","Πολυπλοκότητα","Algorithms","Complexity","DEFAULT LOGIC","INHERITANCE NETWORKS","KNOWLEDGE REPRESENTATION ANDREASONING","NONMONOTONIC LOGICS","Φυσικές Επιστήμες","Επιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική","Natural Sciences","Computer and Information Sciences"],"dc:title":["ΕΛΛΕΙΠΤΙΚΗ ΣΥΜΠΕΡΑΣΜΑΤΟΛΟΓΙΑ: ΠΟΛΥΠΛΟΚΟΤΗΤΑ, ΑΛΓΟΡΙΘΜΟΙ, ΣΗΜΑΣΙΟΛΟΓΙΑ","DEFAULT REASONING: COMPLEXITY, ALGORITHMS, SEMANTICS"],"dc:type":["PhD Thesis"]},"updated_at":"2026-11-18T20:21:24Z"}