BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//labri.fr//NONSGML kigkonsult.se iCalcreator 2.41.92//
CALSCALE:GREGORIAN
METHOD:PUBLISH
UID:a0921e29-4db4-473d-b0b3-836069b1eb03
X-WR-CALNAME:[LX] Edwin Hamel de Le Court
X-WR-TIMEZONE:Europe/Paris
BEGIN:VTIMEZONE
TZID:Europe/Paris
TZUNTIL:20241027T010000Z
BEGIN:STANDARD
TZNAME:CET
DTSTART:20221030T030000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
RDATE:20231029T030000
END:STANDARD
BEGIN:DAYLIGHT
TZNAME:CEST
DTSTART:20230326T020000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
RDATE:20240331T020000
END:DAYLIGHT
END:VTIMEZONE
BEGIN:VEVENT
UID:a0921e29-4db4-473d-b0b3-836069b1eb03
DTSTAMP:20260429T024150Z
CLASS:PUBLIC
DESCRIPTION:*Two-player boundedness counter games* \n\nWe consider two-play
 er zero-sum games with winning objectives beyond regular languages\, expre
 ssed as a parity condition in conjunction with a Boolean combination of bo
 undedness conditions on a finite set of counters which can be incremented\
 , reset to $0$\, but not tested. A boundedness condition requires that a g
 iven counter is bounded along the play. Such games are decidable\, though 
 with non-optimal complexity\, by an encoding into the logic WMSO with the 
 unbounded and path quantifiers\, which is known to be decidable over infin
 ite trees. Our objective is to\ngive tight or tighter complexity results f
 or particular classes of counter games with boundedness conditions\, and s
 tudy their strategy complexity. In particular\, counter games with conjunc
 tion of boundedness conditions are easily seen to be equivalent to Streett
  games\, so\, they are CoNP-c. Moreover\, finite-memory strategies suffice
  for Eve and memoryless strategies suffice for Adam. For counter games wit
 h a disjunction of boundedness conditions\, we prove that they are in solv
 able in NP\cap CoNP\, and in PTime if the parity condition is fixed. In th
 at case memoryless strategies suffice for Eve while infinite memory strate
 gies might be necessary for Adam. Finally\, we consider an extension of th
 ose games with a max operation. In that case\, the complexity increases: f
 or conjunctions of boundedness conditions\, counter games are EXPTIME-c.
DTSTART;TZID=Europe/Paris:20230427T130000
DTEND;TZID=Europe/Paris:20230427T140000
LOCATION:LaBRI
SEQUENCE:0
SUMMARY:[LX] Edwin Hamel de Le Court
TRANSP:OPAQUE
END:VEVENT
END:VCALENDAR
