文章基本信息

标题：Observation and Distinction. Representing Information in Infinite Games
本地全文：下载
作者：Dietmar Berwanger ; Laurent Doyen
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：154
页码：48:1-48:17
DOI：10.4230/LIPIcs.STACS.2020.48
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We compare two approaches for modelling imperfect information in infinite games by using finite-state automata. The first, more standard approach views information as the result of an observation process driven by a sequential Mealy machine. In contrast, the second approach features indistinguishability relations described by synchronous two-tape automata. The indistinguishability-relation model turns out to be strictly more expressive than the one based on observations. We present a characterisation of the indistinguishability relations that admit a representation as a finite-state observation function. We show that the characterisation is decidable, and give a procedure to construct a corresponding Mealy machine whenever one exists.
关键词：Infinite Games on Finite Graphs; Imperfect Information; Automatic Structures