On model-theoretic approaches to monadic second-order logic evaluation
| dc.contributor.author | Κοσμαδάκης, Σταύρος | |
| dc.contributor.author | Φουστούκου, Ευγενία | |
| dc.contributor.other | Cosmadakis, Stavros | |
| dc.contributor.other | Foustoucos, Eugenie | |
| dc.date.accessioned | 2014-01-13T11:42:48Z | |
| dc.date.available | 2014-01-13T11:42:48Z | |
| dc.date.copyright | 2013-10-30 | |
| dc.date.issued | 2014-01-13 | |
| dc.description.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. | el |
| dc.description.translatedabstract | -- | el |
| dc.identifier.uri | http://hdl.handle.net/10889/6583 | |
| dc.language.iso | en | el |
| dc.subject.alternative | Monadic second-order logic (MSO) evaluation problem | el |
| dc.subject.alternative | MSO queries | el |
| dc.subject.alternative | Model-checking | el |
| dc.subject.alternative | Classes of structures of bounded tree-width | el |
| dc.subject.alternative | MSOL-inductive classes of structures | el |
| dc.subject.alternative | Tree automata | el |
| dc.subject.alternative | Parse trees | el |
| dc.subject.alternative | Compositionality | el |
| dc.subject.alternative | Ehrenfeucht-Fraisse games | el |
| dc.subject.alternative | Datalog programs/queries | el |
| dc.title | On model-theoretic approaches to monadic second-order logic evaluation | el |
| dc.type | Technical Report | el |