On model-theoretic approaches to monadic second-order logic evaluation
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...
| Κύριοι συγγραφείς: | , |
|---|---|
| Άλλοι συγγραφείς: | |
| Μορφή: | Technical Report |
| Γλώσσα: | English |
| Έκδοση: |
2014
|
| Θέματα: | |
| Διαθέσιμο Online: | http://hdl.handle.net/10889/6583 |
| id |
nemertes-10889-6583 |
|---|---|
| record_format |
dspace |
| spelling |
nemertes-10889-65832022-09-05T20:21:51Z On model-theoretic approaches to monadic second-order logic evaluation Κοσμαδάκης, Σταύρος Φουστούκου, Ευγενία Cosmadakis, Stavros Foustoucos, Eugenie 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 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. -- 2014-01-13T11:42:48Z 2014-01-13T11:42:48Z 2013-10-30 2014-01-13 Technical Report http://hdl.handle.net/10889/6583 en application/pdf |
| institution |
UPatras |
| collection |
Nemertes |
| language |
English |
| topic |
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 |
| spellingShingle |
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 Κοσμαδάκης, Σταύρος Φουστούκου, Ευγενία On model-theoretic approaches to monadic second-order logic evaluation |
| description |
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. |
| author2 |
Cosmadakis, Stavros |
| author_facet |
Cosmadakis, Stavros Κοσμαδάκης, Σταύρος Φουστούκου, Ευγενία |
| format |
Technical Report |
| author |
Κοσμαδάκης, Σταύρος Φουστούκου, Ευγενία |
| author_sort |
Κοσμαδάκης, Σταύρος |
| title |
On model-theoretic approaches to monadic second-order logic evaluation |
| title_short |
On model-theoretic approaches to monadic second-order logic evaluation |
| title_full |
On model-theoretic approaches to monadic second-order logic evaluation |
| title_fullStr |
On model-theoretic approaches to monadic second-order logic evaluation |
| title_full_unstemmed |
On model-theoretic approaches to monadic second-order logic evaluation |
| title_sort |
on model-theoretic approaches to monadic second-order logic evaluation |
| publishDate |
2014 |
| url |
http://hdl.handle.net/10889/6583 |
| work_keys_str_mv |
AT kosmadakēsstauros onmodeltheoreticapproachestomonadicsecondorderlogicevaluation AT phoustoukoueugenia onmodeltheoreticapproachestomonadicsecondorderlogicevaluation |
| _version_ |
1771297326398177280 |
