Logical Approaches to Computational Barriers

Expressive Power Of Graph Logic

Speaker:
| Timos Antonopoulos |

Slot: |
Array, 16:30-16:50, col. 4 |

We present results on the expressive power of Graph Logic, a spatial logic for querying graphs introduced by (Cardelli, Gardner and Ghelli, ICALP 2002) and studied further by (Dawar, Gardner and Ghelli, Information and Computation v.205). Graph Logic is an extension of First Order Logic with a second order quantifier over edges of restricted form, and a first order quantifier over labels of edges. In particular, if G is some graph, all one can do with the second order quantifier is express that there exists a set of edges X of the graph G such that some formula $\phi$ is satisfied by the subgraph of G containing exactly the edges in X, and some formula $\psi$ is satisfied by the subgraph of G with exactly the remaining edges not in X. It has been observed that GL is a sublogic of Monadic Second Order Logic with quantification over edges and additional first order quantification over edge labels (MSO for short). Although it seems that GL is strictly less expressive than MSO, many interesting properties have been shown to be expressible in GL. Furthermore it was shown in (Dawar, Gardner and Ghelli, Information and Computation v.205) that GL is able to express complete problems on any level of the Polynomial Hierarchy and that GL and MSO are equi-expressive when restricted to words. Marcinkowski (CSL 2006) showed that this richer form of MSO with quantification over edge labels, is more expressive than GL. As this richer form of MSO is not the one we usually deal with, the case where we omit the first order quantification over edge labels from both logics is a more interesting one. We show that this restriction of GL is indeed strictly less expressive than the one of MSO. Moreover we show that this is the case even when restricted to the class of forests.

websites: Arnold Beckmann | 2008-05-19 |