On model-theoretic approaches to monadic second-order logic evaluation

• Κύριοι συγγραφείς: Κοσμαδάκης, Σταύρος, Φουστούκου, Ευγενία
• Άλλοι συγγραφείς: Cosmadakis, Stavros
• Μορφή: Technical Report
• Γλώσσα: English
• Έκδοση: 2014
• Θέματα: Monadic second-order logic (MSO) evaluation problem; MSO queries; Model-checking; Classes of structures of bounded tree-width; MSOL-inductive classes of structures; Tree automata; Parse trees; Compositionality; Ehrenfeucht-Fraisse games; Datalog programs/queries

We review the model-theoretic approaches to Monadic Second-Order Logic (MSO) evaluation, especially to model-checking on MSOL-inductive classes of structures. Starting our study with finite strings and finite trees, we then focus on classes of structures of bounded treewidth. For these classes...