{"id":{"repo_id":"athens","oai_identifier":"oai:lib.uoa.gr:uoadl:1317543"},"canonical_url":"https://search.ndltd.org/etd/athens/oai:lib.uoa.gr:uoadl:1317543","repository":{"repo_id":"athens","name":"National and Kapodistrian University of Athens","base_url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh"},"display":{"title":"Έλεγχος της Συνέπειας Δικτύων Ποιοτικών Χωρικών Περιορισμών με Χρήση Χορδικών Γράφων","abstract":"Ο Λογισμός Σύνδεσης Περιοχών (RCC) είναι η κυρίαρχη προσέγγιση στην Τεχνητή Νοημοσύνη για την αναπαράσταση και την αιτιολόγηση τοπολογικών σχέσεων. Ο RCC λογισμός μπορεί να χρησιμοποιηθεί για να περιγράψει περιοχές που είναι μη-κενά, ανελλιπή υποσύνολα ενός τοπολογικού χώρου μέσω της δήλωσης των τοπολογικών σχέσεων μεταξύ αυτών. Η περισσότερη δημοσιευμένη δουλειά σε αυτό το πεδίο κάνει χρήση ενός υπουνόλου του λογισμού RCC, το οποίο ονομάζεται RCC-8. Το υποσύνολο RCC-8 θεωρεί τις ακόλουθες 8 δυαδικές τοπολογικές σχέσεις: ασύνδετος (DC), εξωτερικά συνδεδεμένος (EC), ίσος (EQ), μερικώς αλληλεπικαλυπτόμενος (PO), εφαπτόμενα εσωκλειόμενος (TPP), εφαπτόμενα εσωκλειόμενος αντίστροφος (TPPi), μη- εφαπτόμενα εσωκλειόμενος (NTPP), μη-εφαπτόμενα εσωκλειόμενος αντίστροφος (NTPPi). Θεωρούμε χορδικά RCC-8 δίκτυα και δείχνουμε πως μπορούμε να ελέγξουμε την συνέπειά τους με την επιβολή μερικές συνέπειας μονοπατιού με αδύναμη σύνθεση. Το αποδεικνύουμε αυτοό χρησιμοποιώντας το δεδομένο πως τα RCC-8 δίκτυα με σχέσεις από τα μέγιστα βατά υποσύνολα H8, C8, και Q8 του RCC-8 έχουν την ιδιότητα της αμαλγάμωσης. Η χρήση της μερικής συνέπειας μονοπατιού έχει σημαντικά πρακτικά επακόλουθα τα οποία επιδεικνύουμε με την υλοποίηση του νέου προγράμματος συλλογιστικής PyRCC8+. Δοθέντος ενός RCC-8 δικτύου με αποκλειστικά βατές RCC-8 σχέσεις, δείχνουμε ότι μπορεί να επιλθυεί πολ΄θ αποδοτικά τριγωνοποιώντας τον υποκείμενο γράφο περιορισμών και εφαρμόζοντας την συνέπεια μονοπατιού σε αυτό τον αραιό γράφο έν αντιθέσει με την πλήρωση του συγκεκριμένου δικτύου. Κατά τον ίδιο τρόπο, η μερική συνέπεια μονοπατιού μπορεί να χρησιμοποιηθεί ως το βήμα ελέγχου συνέπειας σε αλγόριθμους υπαναχώρησης για δίκτυα αυθαίρετων RCC-8 σχέσεων με αποτέλεσμα την βελτιωμένη απόδοση για αραιά δίκτυα, ενώ υπόκειται σε ποινή για πυκνά δίκτυα.","abstract_html":"Ο Λογισμός Σύνδεσης Περιοχών (RCC) είναι η κυρίαρχη προσέγγιση στην Τεχνητή Νοημοσύνη για την αναπαράσταση και την αιτιολόγηση τοπολογικών σχέσεων. Ο RCC λογισμός μπορεί να χρησιμοποιηθεί για να περιγράψει περιοχές που είναι μη-κενά, ανελλιπή υποσύνολα ενός τοπολογικού χώρου μέσω της δήλωσης των τοπολογικών σχέσεων μεταξύ αυτών. Η περισσότερη δημοσιευμένη δουλειά σε αυτό το πεδίο κάνει χρήση ενός υπουνόλου του λογισμού RCC, το οποίο ονομάζεται RCC-8. Το υποσύνολο RCC-8 θεωρεί τις ακόλουθες 8 δυαδικές τοπολογικές σχέσεις: ασύνδετος (DC), εξωτερικά συνδεδεμένος (EC), ίσος (EQ), μερικώς αλληλεπικαλυπτόμενος (PO), εφαπτόμενα εσωκλειόμενος (TPP), εφαπτόμενα εσωκλειόμενος αντίστροφος (TPPi), μη- εφαπτόμενα εσωκλειόμενος (NTPP), μη-εφαπτόμενα εσωκλειόμενος αντίστροφος (NTPPi). Θεωρούμε χορδικά RCC-8 δίκτυα και δείχνουμε πως μπορούμε να ελέγξουμε την συνέπειά τους με την επιβολή μερικές συνέπειας μονοπατιού με αδύναμη σύνθεση. Το αποδεικνύουμε αυτοό χρησιμοποιώντας το δεδομένο πως τα RCC-8 δίκτυα με σχέσεις από τα μέγιστα βατά υποσύνολα H8, C8, και Q8 του RCC-8 έχουν την ιδιότητα της αμαλγάμωσης. Η χρήση της μερικής συνέπειας μονοπατιού έχει σημαντικά πρακτικά επακόλουθα τα οποία επιδεικνύουμε με την υλοποίηση του νέου προγράμματος συλλογιστικής PyRCC8+. Δοθέντος ενός RCC-8 δικτύου με αποκλειστικά βατές RCC-8 σχέσεις, δείχνουμε ότι μπορεί να επιλθυεί πολ΄θ αποδοτικά τριγωνοποιώντας τον υποκείμενο γράφο περιορισμών και εφαρμόζοντας την συνέπεια μονοπατιού σε αυτό τον αραιό γράφο έν αντιθέσει με την πλήρωση του συγκεκριμένου δικτύου. Κατά τον ίδιο τρόπο, η μερική συνέπεια μονοπατιού μπορεί να χρησιμοποιηθεί ως το βήμα ελέγχου συνέπειας σε αλγόριθμους υπαναχώρησης για δίκτυα αυθαίρετων RCC-8 σχέσεων με αποτέλεσμα την βελτιωμένη απόδοση για αραιά δίκτυα, ενώ υπόκειται σε ποινή για πυκνά δίκτυα.","abstract_has_math":false,"creators":["Σιούτης Μιχαήλ"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2012,"date_issued":"2012","date_published":"2012","updated_at":"2026-11-19T05:25:06Z","subjects":[],"languages":["English"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:1317543"],"render_values":[{"text":"uoadl:1317543","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/1317543","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/1317543","record_label":"Repository record","record_kind":"record","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://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh?verb=GetRecord&metadataPrefix=oai_dc&identifier=oai%3Alib.uoa.gr%3Auoadl%3A1317543","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":["2012"]},{"key":"dc:type","label":"Dc Type","values":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["English"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:1317543","https://pergamos.lib.uoa.gr/uoa/dl/object/1317543"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Ο Λογισμός Σύνδεσης Περιοχών (RCC) είναι η κυρίαρχη προσέγγιση στην Τεχνητή Νοημοσύνη για την αναπαράσταση και την αιτιολόγηση τοπολογικών σχέσεων. Ο RCC λογισμός μπορεί να χρησιμοποιηθεί για να περιγράψει περιοχές που είναι μη-κενά, ανελλιπή υποσύνολα ενός τοπολογικού χώρου μέσω της δήλωσης των τοπολογικών σχέσεων μεταξύ αυτών. Η περισσότερη δημοσιευμένη δουλειά σε αυτό το πεδίο κάνει χρήση ενός υπουνόλου του λογισμού RCC, το οποίο ονομάζεται RCC-8. Το υποσύνολο RCC-8 θεωρεί τις ακόλουθες 8 δυαδικές τοπολογικές σχέσεις: ασύνδετος (DC), εξωτερικά συνδεδεμένος (EC), ίσος (EQ), μερικώς αλληλεπικαλυπτόμενος (PO), εφαπτόμενα εσωκλειόμενος (TPP), εφαπτόμενα εσωκλειόμενος αντίστροφος (TPPi), μη- εφαπτόμενα εσωκλειόμενος (NTPP), μη-εφαπτόμενα εσωκλειόμενος αντίστροφος (NTPPi). Θεωρούμε χορδικά RCC-8 δίκτυα και δείχνουμε πως μπορούμε να ελέγξουμε την συνέπειά τους με την επιβολή μερικές συνέπειας μονοπατιού με αδύναμη σύνθεση. Το αποδεικνύουμε αυτοό χρησιμοποιώντας το δεδομένο πως τα RCC-8 δίκτυα με σχέσεις από τα μέγιστα βατά υποσύνολα H8, C8, και Q8 του RCC-8 έχουν την ιδιότητα της αμαλγάμωσης. Η χρήση της μερικής συνέπειας μονοπατιού έχει σημαντικά πρακτικά επακόλουθα τα οποία επιδεικνύουμε με την υλοποίηση του νέου προγράμματος συλλογιστικής PyRCC8+. Δοθέντος ενός RCC-8 δικτύου με αποκλειστικά βατές RCC-8 σχέσεις, δείχνουμε ότι μπορεί να επιλθυεί πολ΄θ αποδοτικά τριγωνοποιώντας τον υποκείμενο γράφο περιορισμών και εφαρμόζοντας την συνέπεια μονοπατιού σε αυτό τον αραιό γράφο έν αντιθέσει με την πλήρωση του συγκεκριμένου δικτύου. Κατά τον ίδιο τρόπο, η μερική συνέπεια μονοπατιού μπορεί να χρησιμοποιηθεί ως το βήμα ελέγχου συνέπειας σε αλγόριθμους υπαναχώρησης για δίκτυα αυθαίρετων RCC-8 σχέσεων με αποτέλεσμα την βελτιωμένη απόδοση για αραιά δίκτυα, ενώ υπόκειται σε ποινή για πυκνά δίκτυα.","The Region Connection Calculus (RCC) is the dominant Artificial Intelligence approach for representing and reasoning about topological relations. RCC can be used to describe regions that are nonempty regular subsets of some topological space by stating their topological relations to each other. Most of the published work in this area deals with a subset of RCC, namely, RCC8. RCC8 considers the following 8 binary topological relations: disconnected (DC), externally connected (EC), equal (EQ), partially overlapping (PO), tangential proper part (TPP), tangential proper part inverse (TPPi), nontangential proper part (NTPP), and nontangential proper part inverse (NTPPi). We consider chordal RCC8 networks and show that we can check their consistency by enforcing partial path consistency with weak composition. We prove this by using the fact that RCC8 networks with relations from the maximal tractable subsets H8, C8, and Q8 of RCC8 have the patchwork property. The use of partial path consistency has important practical consequences that we demonstrate with the implementation of the new reasoner PyRCC85. Given an RCC8 network with only tractable RCC8 relations, we show that it can be solved very efficiently with PyRCC8+ by making its underlying constraint graph chordal and running path consistency on this sparse graph instead of the completion of the given network. In the same way, partial path consistency can be used as the consistency checking step in backtracking algorithms for networks with arbitrary RCC8 relations resulting in very improved pruning for sparse networks while incurring a penalty for dense networks."]},{"key":"dc:title","label":"Title","values":["Έλεγχος της Συνέπειας Δικτύων Ποιοτικών Χωρικών Περιορισμών με Χρήση Χορδικών Γράφων"]}]}],"canonical_facts":{"dc:creator":["Σιούτης Μιχαήλ"],"dc:date":["2012"],"dc:description":["Ο Λογισμός Σύνδεσης Περιοχών (RCC) είναι η κυρίαρχη προσέγγιση στην Τεχνητή Νοημοσύνη για την αναπαράσταση και την αιτιολόγηση τοπολογικών σχέσεων. Ο RCC λογισμός μπορεί να χρησιμοποιηθεί για να περιγράψει περιοχές που είναι μη-κενά, ανελλιπή υποσύνολα ενός τοπολογικού χώρου μέσω της δήλωσης των τοπολογικών σχέσεων μεταξύ αυτών. Η περισσότερη δημοσιευμένη δουλειά σε αυτό το πεδίο κάνει χρήση ενός υπουνόλου του λογισμού RCC, το οποίο ονομάζεται RCC-8. Το υποσύνολο RCC-8 θεωρεί τις ακόλουθες 8 δυαδικές τοπολογικές σχέσεις: ασύνδετος (DC), εξωτερικά συνδεδεμένος (EC), ίσος (EQ), μερικώς αλληλεπικαλυπτόμενος (PO), εφαπτόμενα εσωκλειόμενος (TPP), εφαπτόμενα εσωκλειόμενος αντίστροφος (TPPi), μη- εφαπτόμενα εσωκλειόμενος (NTPP), μη-εφαπτόμενα εσωκλειόμενος αντίστροφος (NTPPi). Θεωρούμε χορδικά RCC-8 δίκτυα και δείχνουμε πως μπορούμε να ελέγξουμε την συνέπειά τους με την επιβολή μερικές συνέπειας μονοπατιού με αδύναμη σύνθεση. Το αποδεικνύουμε αυτοό χρησιμοποιώντας το δεδομένο πως τα RCC-8 δίκτυα με σχέσεις από τα μέγιστα βατά υποσύνολα H8, C8, και Q8 του RCC-8 έχουν την ιδιότητα της αμαλγάμωσης. Η χρήση της μερικής συνέπειας μονοπατιού έχει σημαντικά πρακτικά επακόλουθα τα οποία επιδεικνύουμε με την υλοποίηση του νέου προγράμματος συλλογιστικής PyRCC8+. Δοθέντος ενός RCC-8 δικτύου με αποκλειστικά βατές RCC-8 σχέσεις, δείχνουμε ότι μπορεί να επιλθυεί πολ΄θ αποδοτικά τριγωνοποιώντας τον υποκείμενο γράφο περιορισμών και εφαρμόζοντας την συνέπεια μονοπατιού σε αυτό τον αραιό γράφο έν αντιθέσει με την πλήρωση του συγκεκριμένου δικτύου. Κατά τον ίδιο τρόπο, η μερική συνέπεια μονοπατιού μπορεί να χρησιμοποιηθεί ως το βήμα ελέγχου συνέπειας σε αλγόριθμους υπαναχώρησης για δίκτυα αυθαίρετων RCC-8 σχέσεων με αποτέλεσμα την βελτιωμένη απόδοση για αραιά δίκτυα, ενώ υπόκειται σε ποινή για πυκνά δίκτυα.","The Region Connection Calculus (RCC) is the dominant Artificial Intelligence approach for representing and reasoning about topological relations. RCC can be used to describe regions that are nonempty regular subsets of some topological space by stating their topological relations to each other. Most of the published work in this area deals with a subset of RCC, namely, RCC8. RCC8 considers the following 8 binary topological relations: disconnected (DC), externally connected (EC), equal (EQ), partially overlapping (PO), tangential proper part (TPP), tangential proper part inverse (TPPi), nontangential proper part (NTPP), and nontangential proper part inverse (NTPPi). We consider chordal RCC8 networks and show that we can check their consistency by enforcing partial path consistency with weak composition. We prove this by using the fact that RCC8 networks with relations from the maximal tractable subsets H8, C8, and Q8 of RCC8 have the patchwork property. The use of partial path consistency has important practical consequences that we demonstrate with the implementation of the new reasoner PyRCC85. Given an RCC8 network with only tractable RCC8 relations, we show that it can be solved very efficiently with PyRCC8+ by making its underlying constraint graph chordal and running path consistency on this sparse graph instead of the completion of the given network. In the same way, partial path consistency can be used as the consistency checking step in backtracking algorithms for networks with arbitrary RCC8 relations resulting in very improved pruning for sparse networks while incurring a penalty for dense networks."],"dc:identifier":["uoadl:1317543","https://pergamos.lib.uoa.gr/uoa/dl/object/1317543"],"dc:language":["English"],"dc:title":["Έλεγχος της Συνέπειας Δικτύων Ποιοτικών Χωρικών Περιορισμών με Χρήση Χορδικών Γράφων"],"dc:type":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]},"updated_at":"2026-11-19T05:25:06Z"}