Unit:
Τομέας Μαθηματικής ΑνάλυσηςLibrary of the School of Science
Author:
Καλαντζή Λαμπρινή
Dissertation committee:
Φουστούκου Ε. Επίκ. Καθηγήτρια Οικονομικού Πανεπιστημίου Αθηνών (επιβλέπουσα), Κοσμαδάκης Σ. Καθηγητής Πανεπιστημίου Πατρών, Irene Guessarian Καθηγήτρια Universite Paris Diderot (Paris 7) - Liafa
Original Title:
Μοναδιαία δευτεροβάθμια λογική και παραμετρική πολυπλοκότητα σε δομές φραγμένου δεντροπλάτους
Summary:
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.
Keywords:
Monadic second-Order logic (MSO), Tree automata, Datalog, Treewidth
Number of index pages:
155-157
Number of pages:
xii, 162
