LILaC - paper abstract

Global and local graph modifiers

Aucher, Guillaume and Balbiani, Philippe and Fariñas Del Cerro, Luis and Herzig, Andreas},

Abstract:

We define two modal logics that allow to reason about modifications of graphs. Both have a universal modal operator. The first one only involves global modifications (of some state label, or of some edge label) everywhere in the graph. The second one also allows for modifications that are local to states. The global version generalizes logics of public announcements and public assignments, as well as a logic of preference modification introduced by van Benthem et Liu. By means of reduction axioms we show that it is just as expressive as the underlying logic without global modifiers. We then show that adding local modifiers dramatically increases the power of the logic: the logic of global and local modifiers is undecidable. We finally study its relation with hybrid logic with binder.

PDF

Note:

A preliminary versions of the paper was presented at the M4M'2007 workshop (PDF).

A follow-up paper was presented at ICGT-2010.

Bibtex-entry:



@Article{AucherBalbianiFarinasHerzig-Entcs09,
author    = {Aucher, Guillaume and Balbiani, Philippe and Fariñas Del Cerro, Luis and Herzig, Andreas},
title     = "{Global and local graph modifiers}",
journal   = "{Electronic Notes in Theoretical Computer Science (ENTCS), Special issue
``Proceedings of the 5th Workshop on Methods for Modalities (M4M5 2007)'' }",
publisher = {Elsevier},
year      = {2009},
volume    = {231},
pages     = {293--307},
keywords = {Public announcement logic, graph modifiers},
}

https://www.irit.fr/~Andreas.Herzig