---
res:
  bibo_abstract:
  - 'First cycle games (FCG) are played on a finite graph by two players who push
    a token along the edges until a vertex is repeated, and a simple cycle is formed.
    The winner is determined by some fixed property Y of the sequence of labels of
    the edges (or nodes) forming this cycle. These games are traditionally of interest
    because of their connection with infinite-duration games such as parity and mean-payoff
    games. We study the memory requirements for winning strategies of FCGs and certain
    associated infinite duration games. We exhibit a simple FCG that is not memoryless
    determined (this corrects a mistake in Memoryless determinacy of parity and mean
    payoff games: a simple proof by Bj⋯orklund, Sandberg, Vorobyov (2004) that claims
    that FCGs for which Y is closed under cyclic permutations are memoryless determined).
    We show that θ (n)! memory (where n is the number of nodes in the graph), which
    is always sufficient, may be necessary to win some FCGs. On the other hand, we
    identify easy to check conditions on Y (i.e., Y is closed under cyclic permutations,
    and both Y and its complement are closed under concatenation) that are sufficient
    to ensure that the corresponding FCGs and their associated infinite duration games
    are memoryless determined. We demonstrate that many games considered in the literature,
    such as mean-payoff, parity, energy, etc., satisfy these conditions. On the complexity
    side, we show (for efficiently computable Y) that while solving FCGs is in PSPACE,
    solving some families of FCGs is PSPACE-hard. @eng'
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Benjamin
      foaf_name: Aminof, Benjamin
      foaf_surname: Aminof
      foaf_workInfoHomepage: http://www.librecat.org/personId=4A55BD00-F248-11E8-B48F-1D18A9856A87
  - foaf_Person:
      foaf_givenName: Sasha
      foaf_name: Rubin, Sasha
      foaf_surname: Rubin
      foaf_workInfoHomepage: http://www.librecat.org/personId=2EC51194-F248-11E8-B48F-1D18A9856A87
  bibo_doi: 10.4204/EPTCS.146.11
  bibo_volume: 146
  dct_date: 2014^xs_gYear
  dct_language: eng
  dct_publisher: Open Publishing Association@
  dct_title: First cycle games@
...