Abstract
Bisimulations are a key notion to study the expressive power of a modal language. This paper studies the expressivity of Game Description Language (GDL) and its epistemic extension Epistemic GDL (EGDL) through a bisimulation approach. We first define a notion of bisimulation for GDL and prove that it coincides with the indistinguishability of GDL formulas. Based on it, we establish a characterization of the definability of GDL in terms of k-bisimulations. Then we design novel notions of bisimulation for EGDL and obtain characterizations of the expressive power of EGDL in terms of them. These characterizations provide a powerful tool to identify the expressive power of game description languages. Finally, we demonstrate with real games that bisimulation can be generalized to capture a wide range of game equivalence.
Original language | English |
---|---|
Pages (from-to) | 163-187 |
Number of pages | 25 |
Journal | Journal of Logic and Computation |
Volume | 33 |
Issue number | 1 |
DOIs | |
Publication status | Published - 1 Jan 2023 |
Bibliographical note
Publisher Copyright:© The Author(s) 2022. Published by Oxford University Press.
Notes
WIP in RDKeywords
- game description languages
- Bisimulation
- game equivalence
- general game playing
- expressive power