Deprecated: Function split() is deprecated in /srv/www/htdocs-cs/cie08/db-code.php on line 107

Deprecated: Function split() is deprecated in /srv/www/htdocs-cs/cie08/db-code.php on line 117
CiE 2008 - Regular Talk: - Expressive Power Of Graph Logic
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


Notice: Use of undefined constant session - assumed 'session' in /srv/www/htdocs-cs/cie08/conf-code.php on line 440

Notice: Use of undefined constant slot - assumed 'slot' in /srv/www/htdocs-cs/cie08/conf-code.php on line 441

Notice: Use of undefined constant room - assumed 'room' in /srv/www/htdocs-cs/cie08/conf-code.php on line 442
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
Warning: date(): It is not safe to rely on the system's timezone settings. You are *required* to use the date.timezone setting or the date_default_timezone_set() function. In case you used any of those methods and you are still getting this warning, you most likely misspelled the timezone identifier. We selected the timezone 'UTC' for now, but please set date.timezone to select your timezone. in /srv/www/htdocs-cs/cie08/conf-code.php on line 136
2008-05-19 Valid HTML 4.01! Valid CSS!