Computability in Europe 2008
Logic and Theory of Algorithms

Print current page  Print this page

Regular Talk:
Expressive Power Of Graph Logic

Edit abstract data

Speaker: Timos Antonopoulos
Slot: Wed, 16:30-16:50, Room 22 (col. 4)

Abstract

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 Valid HTML 4.01! Valid CSS!