首页    期刊浏览 2024年09月18日 星期三
登录注册

文章基本信息

  • 标题:How do we remember the past in randomised strategies?
  • 本地全文:下载
  • 作者:Julien Cristau ; Claire David ; Florian Horn
  • 期刊名称:Electronic Proceedings in Theoretical Computer Science
  • 电子版ISSN:2075-2180
  • 出版年度:2010
  • 卷号:25
  • 页码:30-39
  • DOI:10.4204/EPTCS.25.7
  • 出版社:Open Publishing Association
  • 摘要:Graph games of infinite length are a natural model for open reactive processes: one player represents the controller, trying to ensure a given specification, and the other represents a hostile environment. The evolution of the system depends on the decisions of both players, supplemented by chance.

    In this work, we focus on the notion of randomised strategy. More specifically, we show that three natural definitions may lead to very different results: in the most general cases, an almost-surely winning situation may become almost-surely losing if the player is only allowed to use a weaker notion of strategy. In more reasonable settings, translations exist, but they require infinite memory, even in simple cases. Finally, some traditional problems becomes undecidable for the strongest type of strategies.

国家哲学社会科学文献中心版权所有