Which Semantics for Neighbourhood Semantics?

C. Areces and D. Figueira. Which Semantics for Neighbourhood Semantics?. In Proceedigns of IJCAI 09, pp. 671–676, Pasadena, California, USA, 2009.

Download

[pdf] 

Abstract

In this article we discuss two alternative proposals for neighbourhood semantics (which we call strict and loose neighbourhood semantics, N_= and N_\subseteq respectively) that have been previously introduced in the literature. Our main tools are suitable notions of bisimulation. While an elegant notion of bisimulation exists for N_\subseteq, the required bisimulation for N_= is rather involved. We propose a simple extension of N_= with a universal modality that we call N_=(E), which comes together with a natural notion of bisimulation. We also investigate the complexity of the satisfiability problem for N_\subseteq and N_=(E).

BibTeX

@InCollection{Areces2009,
  author =       "C. Areces and D. Figueira",
  booktitle =    "Proceedigns of IJCAI 09",
  title =        "Which Semantics for Neighbourhood Semantics?",
  year =         "2009",
  address =      "Pasadena, California, USA",
  pages =        "671--676",
  abstract =     "In this article we discuss two alternative proposals
                 for neighbourhood semantics (which we call strict and
                 loose neighbourhood semantics, N_= and N_\subseteq
                 respectively) that have been previously introduced in
                 the literature. Our main tools are suitable notions of
                 bisimulation. While an elegant notion of bisimulation
                 exists for N_\subseteq, the required bisimulation for
                 N_= is rather involved. We propose a simple extension
                 of N_= with a universal modality that we call N_=(E),
                 which comes together with a natural notion of
                 bisimulation. We also investigate the complexity of the
                 satisfiability problem for N_\subseteq and N_=(E).",
  ISBN =         "978-1-57735-426-0",
}