TY - GEN
T1 - Bisimulation for neighbourhood structures
AU - Hansen, Helle Hvid
AU - Kupke, Clemens
AU - Pacuit, Eric
PY - 2007
Y1 - 2007
N2 - Neighbourhood structures are the standard semantic tool used to reason about non-normal modal logics. In coalgebraic terms, a neighbourhood frame is a coalgebra for the contravariant powerset functor composed with itself, denoted by 22. In our paper, we investigate the coalgebraic equivalence notions of 22-bisimulation, behavioural equivalence and neighbourhood bisimulation (a notion based on pushouts), with the aim of finding the logically correct notion of equivalence on neighbourhood structures. Our results include relational characterisations for 22-bisimulation and neighbourhood bisimulation, and an analogue of Van Benthem's characterisation theorem for all three equivalence notions. We also show that behavioural equivalence gives rise to a Hennessy-Milner theorem, and that this is not the case for the other two equivalence notions.
AB - Neighbourhood structures are the standard semantic tool used to reason about non-normal modal logics. In coalgebraic terms, a neighbourhood frame is a coalgebra for the contravariant powerset functor composed with itself, denoted by 22. In our paper, we investigate the coalgebraic equivalence notions of 22-bisimulation, behavioural equivalence and neighbourhood bisimulation (a notion based on pushouts), with the aim of finding the logically correct notion of equivalence on neighbourhood structures. Our results include relational characterisations for 22-bisimulation and neighbourhood bisimulation, and an analogue of Van Benthem's characterisation theorem for all three equivalence notions. We also show that behavioural equivalence gives rise to a Hennessy-Milner theorem, and that this is not the case for the other two equivalence notions.
KW - Behavioural equivalence
KW - Bisimulation
KW - Invariance
KW - Neighbourhood semantics
KW - Non-normal modal logic
UR - http://www.scopus.com/inward/record.url?scp=38049089947&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-73859-6_19
DO - 10.1007/978-3-540-73859-6_19
M3 - Conference contribution
AN - SCOPUS:38049089947
SN - 9783540738572
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 279
EP - 293
BT - Algebra and Coalgebra in Computer Science - Second International Conference, CALCO 2007, Proceedings
PB - Springer
T2 - 2nd International Conference on Algebra and Coalgebra in Computer Science, CALCO 2007
Y2 - 20 August 2007 through 24 August 2007
ER -