Back to search

National and Kapodistrian University of Athens

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

Abstract

dc:description

Στην παρούσα διατριβή, προτείνουμε νέα αυτόματα που εκφράζουν προβλήματα αποτίμησης της Μοναδιαίας Δευτεροβάθμιας Λογικής (MSO), καθώς και νέους αποδοτικούς αλγορίθμους για τα προβλήματα αυτά οι οποίοι βασίζονται στις βάσεις δεδομένων. Εξετάζουμε αρχικά την περίπτωση που οι δεδομένες δομές είναι πεπερασμένα δέντρα και έπειτα ανεξάρτητα την περίπτωση των δομών φραγμένου δεντροπλάτους. Κεντρικό σημείο της προσέγγισής μας σε καθεμία περίπτωση είναι ο επαναπροσδιορισμός της ισοδυναμίας MSO/αυτομάτων μέσω νέων αυτομάτων αναθέσεων που ορίζονται κάθε φορά. Έτσι, ανάγουμε τα αρχικά προβλήματα αποτίμησης της MSO σε ισοδύναμα προβλήματα που αφορούν στα νέα αυτά αυτόματα αναθέσεων. Μέσω της μοντελοποίησης αυτών των τελευταίων προβλημάτων αποτίμησης αυτομάτων σε ένα πλαίσιο βάσεων δεδομένων, επιλύουμε τα αρχικά προβλήματα αποτίμησης της MSO μέσω κατάλληλων αλγορίθμων βελτιστοποίησης από το χώρο των βάσεων δεδομένων.

Degree

thesis:*
Grantor dc:publisher
National and Kapodistrian University of Athens
Year dc:date
2011

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Kalantzi, Lambrini
  • Καλαντζή, Λαμπρινή

Subjects

dc:subject × 8

Rights

Language dc:language
gre

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/30607

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Kalantzi, Lambrini; Καλαντζή, Λαμπρινή. Μοναδιαία δευτεροβάθμια λογική και παραμετρική πολυπλοκότητα σε δομές φραγμένου δεντροπλάτους. National and Kapodistrian University of Athens, 2011. http://hdl.handle.net/10442/hedi/30607