Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision | Next revision Both sides next revision | ||
sav08:graphs_as_interpretations [2008/03/19 16:16] vkuncak |
sav08:graphs_as_interpretations [2008/03/19 16:37] vkuncak |
||
---|---|---|---|
Line 22: | Line 22: | ||
\] | \] | ||
- | Note: there is no formula $F$ in this language ${\cal L} = \{edge\}$ that characterizes property "graph has no cycles". All properties expressed in first-order logic on graphs are "local". | + | Note: there is no formula $F$ in this language ${\cal L} = \{edge\}$ that characterizes property "graph has no cycles". All properties expressed in first-order logic on graphs are "local". Intuitively, formula with $k$ universal quantifiers says that if we pick any set of $k$ vertices in the graph, then they (and their close neighbors) can induce only one of the finitely many specified subgraphs. |
- | + | ||
- | Many more properties become expressible if we take as domain $D$ the set of all subsets of $V$ and allow set operations in our language. | + | |
* [[http://citeseer.ist.psu.edu/benedikt95relational.html|Relational Expressive Power of Constraint Query Language]] | * [[http://citeseer.ist.psu.edu/benedikt95relational.html|Relational Expressive Power of Constraint Query Language]] | ||
* [[http://citeseer.ist.psu.edu/context/64580/0|H. Gaifman, On local and non-local properties, in Logic Colloquium '81, North Holland, 1982]] | * [[http://citeseer.ist.psu.edu/context/64580/0|H. Gaifman, On local and non-local properties, in Logic Colloquium '81, North Holland, 1982]] | ||
+ | |||
+ | Many more properties become expressible if we take as domain $D$ the set of all subsets of $V$ and allow set operations in our language. | ||