δείτε την πρωτότυπη σελίδα τεκμηρίου στον ιστότοπο του αποθετηρίου του φορέα για περισσότερες πληροφορίες και για να δείτε όλα τα ψηφιακά αρχεία του τεκμηρίου*
Μοναδιαία δευτεροβάθμια λογική και παραμετρική πολυπλοκότητα σε δομές φραγμένου δεντροπλάτους
Στην παρούσα διατριβή, προτείνουμε νέα αυτόματα που εκφράζουν προβλήματα
αποτίμησης της Μοναδιαίας Δευτεροβάθμιας Λογικής (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)
*Η εύρυθμη και αδιάλειπτη λειτουργία των διαδικτυακών διευθύνσεων των συλλογών (ψηφιακό αρχείο, καρτέλα τεκμηρίου στο αποθετήριο) είναι αποκλειστική ευθύνη των αντίστοιχων Φορέων περιεχομένου.
Βοηθείστε μας να κάνουμε καλύτερο το OpenArchives.gr.
Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών
