Global and local graph modifiers

Abstract : We dene two modal logics that allow to reason about modications of graphs. Both have a universal modal operator. The rst one only involves global modications (of some state label, or of some edge label) everywhere in the graph. The second one also allows for modications that are local to states. The global version generalizes logics of public announcements and public assignments, as well as a logic of preference modication 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 modiers. We then show that adding local modiers dramatically increases the power of the logic: the logic of global and local modiers is undecidable. We nally study its relation with hybrid logic with binder.
Type de document :
Article dans une revue
Electronic Notes in Theoretical Computer Science, Elsevier, 2009
Liste complète des métadonnées

Littérature citée [13 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00556034
Contributeur : Guillaume Aucher <>
Soumis le : samedi 15 janvier 2011 - 01:40:25
Dernière modification le : mercredi 23 mai 2018 - 17:58:06
Document(s) archivé(s) le : samedi 16 avril 2011 - 02:28:06

Fichier

M4M.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : inria-00556034, version 1

Collections

Citation

Guillaume Aucher, Philippe Balbiani, Luis Farinas del Cerro, Andreas Herzig. Global and local graph modifiers. Electronic Notes in Theoretical Computer Science, Elsevier, 2009. 〈inria-00556034〉

Partager

Métriques

Consultations de la notice

165

Téléchargements de fichiers

103