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

• Main Authors: Καλαντζή, Λαμπρινή, Φουστούκου, Ευγενία
• Other Authors: Kalantzi, Labrini
• Format: Technical Report
• Language: English
• Published: 2011
• Subjects: 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...