Game equivalence and expressive power of game description languages : a bisimulation approach

Guifei Jiang, Laurent Perrussel, Dongmo Zhang, Heng Zhang, Yuzhi Zhang

Research output: Contribution to journalArticlepeer-review

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 languageEnglish
Pages (from-to)163-187
Number of pages25
JournalJournal of Logic and Computation
Volume33
Issue number1
DOIs
Publication statusPublished - 1 Jan 2023

Bibliographical note

Publisher Copyright:
© The Author(s) 2022. Published by Oxford University Press.

Notes

WIP in RD

Keywords

  • game description languages
  • Bisimulation
  • game equivalence
  • general game playing
  • expressive power

Fingerprint

Dive into the research topics of 'Game equivalence and expressive power of game description languages : a bisimulation approach'. Together they form a unique fingerprint.

Cite this