Advanced search
Add to list

On the definability of simulation and bisimulation in epistemic logic

(2014) JOURNAL OF LOGIC AND COMPUTATION. 24(6). p.1209-1227
Author
Organization
Abstract
We explore when finite epistemic models are definable up to simulation or bisimulation, either over the basic multi-agent epistemic language L or over its extension L-C with common knowledge operators. Our main results are the following: (1) Bisimulation to finite epistemic states (i.e. pointed models) is not definable in L. (2) Global bisimulation to finite epistemic models is definable using model validity in L. (3) Simulation by finite epistemic states is not always definable, even over L-C. (4) We identify a class of epistemic models called well-multifounded for which simulation to finite epistemic states is definable over L. The first two results contrasts with that of van Benthem that finite epistemic states are definable up to bisimulation in L-C by so-called characteristic formulae. Our results have applications in the logical specification of multi-agent systems. Characteristic formulae, which define states up to bisimulation, fully capture all modally definable properties of models, and can for example be used to give complete calculi for validity over fixed structures. Meanwhile, simulation is a 'substructure' relation that is appropriate for epistemic logic, as it preserves positive existential formulae. Simulation formulae are useful in giving a dynamic description of models subject to epistemic actions.
Keywords
Kripke semantics, bisimulation, expressiveness, definability

Citation

Please use this url to cite or link to this publication:

MLA
van Ditmarsch, Hans, David Fernández-Duque, and Wiebe van der Hoek. “On the Definability of Simulation and Bisimulation in Epistemic Logic.” JOURNAL OF LOGIC AND COMPUTATION 24.6 (2014): 1209–1227. Print.
APA
van Ditmarsch, H., Fernández-Duque, D., & van der Hoek, W. (2014). On the definability of simulation and bisimulation in epistemic logic. JOURNAL OF LOGIC AND COMPUTATION, 24(6), 1209–1227.
Chicago author-date
van Ditmarsch, Hans, David Fernández-Duque, and Wiebe van der Hoek. 2014. “On the Definability of Simulation and Bisimulation in Epistemic Logic.” Journal of Logic and Computation 24 (6): 1209–1227.
Chicago author-date (all authors)
van Ditmarsch, Hans, David Fernández-Duque, and Wiebe van der Hoek. 2014. “On the Definability of Simulation and Bisimulation in Epistemic Logic.” Journal of Logic and Computation 24 (6): 1209–1227.
Vancouver
1.
van Ditmarsch H, Fernández-Duque D, van der Hoek W. On the definability of simulation and bisimulation in epistemic logic. JOURNAL OF LOGIC AND COMPUTATION. 2014;24(6):1209–27.
IEEE
[1]
H. van Ditmarsch, D. Fernández-Duque, and W. van der Hoek, “On the definability of simulation and bisimulation in epistemic logic,” JOURNAL OF LOGIC AND COMPUTATION, vol. 24, no. 6, pp. 1209–1227, 2014.
@article{8566416,
  abstract     = {We explore when finite epistemic models are definable up to simulation or bisimulation, either over the basic multi-agent epistemic language L or over its extension L-C with common knowledge operators. Our main results are the following: 
(1) Bisimulation to finite epistemic states (i.e. pointed models) is not definable in L. 
(2) Global bisimulation to finite epistemic models is definable using model validity in L. 
(3) Simulation by finite epistemic states is not always definable, even over L-C. 
(4) We identify a class of epistemic models called well-multifounded for which simulation to finite epistemic states is definable over L. 
The first two results contrasts with that of van Benthem that finite epistemic states are definable up to bisimulation in L-C by so-called characteristic formulae. 
Our results have applications in the logical specification of multi-agent systems. Characteristic formulae, which define states up to bisimulation, fully capture all modally definable properties of models, and can for example be used to give complete calculi for validity over fixed structures. Meanwhile, simulation is a 'substructure' relation that is appropriate for epistemic logic, as it preserves positive existential formulae. Simulation formulae are useful in giving a dynamic description of models subject to epistemic actions.},
  author       = {van Ditmarsch, Hans and Fernández-Duque, David and van der Hoek, Wiebe},
  issn         = {0955-792X},
  journal      = {JOURNAL OF LOGIC AND COMPUTATION},
  keywords     = {Kripke semantics,bisimulation,expressiveness,definability},
  language     = {eng},
  number       = {6},
  pages        = {1209--1227},
  title        = {On the definability of simulation and bisimulation in epistemic logic},
  url          = {http://dx.doi.org/10.1093/logcom/exs058},
  volume       = {24},
  year         = {2014},
}

Altmetric
View in Altmetric
Web of Science
Times cited: