Please use this identifier to cite or link to this item:
Title: On model-theoretic approaches to monadic second-order logic evaluation
Authors: Κοσμαδάκης, Σταύρος
Φουστούκου, Ευγενία
Issue Date: 2014-01-13
Keywords (translated): Monadic second-order logic (MSO) evaluation problem
MSO queries
Classes of structures of bounded tree-width
MSOL-inductive classes of structures
Tree automata
Parse trees
Ehrenfeucht-Fraisse games
Datalog programs/queries
Abstract: 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 we define the ``model-theoretical automaton'' which generalizes the corresponding automaton defined by Ladner for strings. First we prove that the model-theoretical automaton cannot be used as an MSO model-checking algorithm on any of these classes of structures. Then we study its relationship with other classical model-theoretic methods as well as its relationship with recent datalog-based approaches to the MSO model-checking problem.
Abstract (translated): --
Appears in Collections:Τμήμα Μηχανικών Η/Υ και Πληροφορικής (Τεχνικές Αναφορές)

Files in This Item:
File Description SizeFormat 
Tech_Report_Cosmadakis_Foustoucos_2013.pdf461.04 kBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.