Automata theoretic and Datalog based solutions of Monadic Second order Logic Evaluation Problems over Structures of bounded treewidth

Automata-theoretic Solution Datalog algorithms for the MSO evaluation problem Automata-theoretic and Datalog-based solutions of MSO Evaluation Problems over Structures of bounded-treewidth Labrini Kalantzi University of Athens (joint work with E. Foustoucos) 2nd Workshop on Graph Decompositions Theoretical, Algorithmic and Logical Aspects October 18-22, 2010 CIRM, Luminy, Marseille CIRM, 18-22 Oct. 2010 Automata & Datalog solutions of MSO Evaluation Problems

• over structures
• datalog algorithms
• theoretic solution
• deterministic bottom-up
• main theorem
• mso evaluation
• direct automata-theoretic reduction
• automata