Global and Local Graph Modifiers
The work
| Authors | Guillaume Aucher; Philippe Balbiani; Luís Fariñas del Cerro; Andreas Herzig |
|---|---|
| Editors | |
| Type | article |
| Year | 2009 |
| Citekey | aucher2009global |
Where it appeared
| Published in | Electronic Notes in Theoretical Computer Science |
|---|---|
| Publisher | Elsevier BV |
| Volume | 231 |
| Pages | 293--307 |
Identifiers
| DOI | 10.1016/j.entcs.2009.02.042 |
|---|---|
| OpenAlex | W2099577392 |
Access
| Landing page | https://doi.org/10.1016/j.entcs.2009.02.042 |
|---|---|
| Free full text | https://www.sciencedirect.com/science/article/pii/S1571066109000474/pdf |
From OpenAlex, which stores abstracts as an index of words and their positions: what is shown is rebuilt from that, and reads fluently whether or not it is what the author wrote.
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.
How it got here
| How it got here | agent via openalex |
|---|---|
| Added | 2026-10-24 15:49 UTC |
| Not denied by | a person 2026-10-29 17:12 UTC |
Filed under
Cite it as
@article{aucher2009global,
title = {Global and Local Graph Modifiers},
author = {Guillaume Aucher and Philippe Balbiani and Luís Fariñas del Cerro and Andreas Herzig},
year = {2009},
journal = {Electronic Notes in Theoretical Computer Science},
publisher = {Elsevier BV},
volume = {231},
pages = {293--307},
doi = {10.1016/j.entcs.2009.02.042},
}
This record lives at https://refs.drheap.org/aucher2009global/ and will keep doing so.