Automata-theoretic and datalog-based solutions of monadic second-order logic evaluation problems over structures of bounded-treewidth

• Κύριοι συγγραφείς: Καλαντζή, Λαμπρινή, Φουστούκου, Ευγενία
• Άλλοι συγγραφείς: Kalantzi, Labrini
• Μορφή: Technical Report
• Γλώσσα: English
• Έκδοση: 2011
• Θέματα: Monadic second-order logic; Tree automata; Datalog; Treewidth

We propose automata-theoretic and datalog-based solutions for the Monadic Second Order (MSO) evaluation problem over finite structures of bounded treewidth, and then extend this approach to MSO-definable optimization problems. More precisely, we introduce decomposition-automata which can be thought...