1. Home page
  2. Search

Μοναδιαία δευτεροβάθμια λογική και παραμετρική πολυπλοκότητα σε δομές φραγμένου δεντροπλάτους

This item is provided by the institution :
/aggregator-openarchives/portal/institutions/uoa   

Repository :
Pergamos Digital Library   

see the original item page
in the repository's web site and access all digital files if the item*



Μοναδιαία δευτεροβάθμια λογική και παραμετρική πολυπλοκότητα σε δομές φραγμένου δεντροπλάτους
Καλαντζή Λαμπρινή (EL)
born_digital_thesis
Διδακτορική Διατριβή (EL)
Doctoral Dissertation (EN)
2013
Στην παρούσα διατριβή, προτείνουμε νέα αυτόματα που εκφράζουν προβλήματα αποτίμησης της Μοναδιαίας Δευτεροβάθμιας Λογικής (MSO), καθώς και νέους αποδοτικούς αλγορίθμους για τα προβλήματα αυτά οι οποίοι βασίζονται στις βάσεις δεδομένων. Εξετάζουμε αρχικά την περίπτωση που οι δεδομένες δομές είναι πεπερασμένα δέντρα και έπειτα ανεξάρτητα την περίπτωση των δομών φραγμένου δεντροπλάτους. Κεντρικό σημείο της προσέγγισής μας σε καθεμία περίπτωση είναι ο επαναπροσδιορισμός της ισοδυναμίας MSO/αυτομάτων μέσω νέων αυτομάτων αναθέσεων που ορίζονται κάθε φορά. Έτσι, ανάγουμε τα αρχικά προβλήματα αποτίμησης της MSO σε ισοδύναμα προβλήματα που αφορούν στα νέα αυτά αυτόματα αναθέσεων. Μέσω της μοντελοποίησης αυτών των τελευταίων προβλημάτων αποτίμησης αυτομάτων σε ένα πλαίσιο βάσεων δεδομένων, επιλύουμε τα αρχικά προβλήματα αποτίμησης της MSO μέσω κατάλληλων αλγορίθμων βελτιστοποίησης από το χώρο των βάσεων δεδομένων. (EL)
In the current thesis we suggest new automata for Monadic Second Order logic (MSO) as well as new efficient algorithms, which are based on Database Theory, for the corresponding MSO-evaluation problems over structures of bounded treewidth. We first consider these MSO-evaluation problems over structures that are finite trees and then independently over structures of bounded treewidth. Central point of the suggested approaches is the reformulation of the MSO/automata equivalence via new assignment automata that we define for each case. So, we reduce the initial MSO evaluation problems into equivalent evaluation problems for assignment automata. Through the modeling of the latter automata evaluation problems into a database context, we solve the initial MSO evaluation problems via proper database optimization algorithms. (EN)
Greek
Σχολή Θετικών Επιστημών » Τμήμα Μαθηματικών » Τομέας Μαθηματικής Ανάλυσης
Βιβλιοθήκη και Κέντρο Πληροφόρησης » Βιβλιοθήκη Σχολής Θετικών Επιστημών
https://creativecommons.org/licenses/by-nc/4.0/
University of Athens
Pergamos Digital Library
Doctoral Dissertation



*Institutions are responsible for keeping their URLs functional (digital file, item page in repository site)