Trading bounds for memory in games with counters

DOI10.1007/978-3-662-47666-6_16MaRDI QIDQ3449476zbMATH OpenOpenAlexFDO

Authors Nathanaël Fijalkow, Florian Horn, Denis Kuperberg, Michał Skrzypczak

Publication date 4 November 2015

Published in Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1709.03121

zbMATH Keywords

trading bounds for memorytwo-player games with counters

Mathematics Subject Classification ID

2-person games (91A05)

Abstract: We study two-player games with counters, where the objective of the first player is that the counter values remain bounded. We investigate the existence of a trade-off between the size of the memory and the bound achieved on the counters, which has been conjectured by Colcombet and Loeding. We show that unfortunately this conjecture does not hold: there is no trade-off between bounds and memory, even for finite arenas. On the positive side, we prove the existence of a trade-off for the special case of thin tree arenas. This allows to extend the theory of regular cost functions over thin trees, and obtain as a corollary the decidability of cost monadic second-order logic over thin trees.

Recommendations

• Playing Safe
• Solving counter parity games
• Resource Reachability Games on Pushdown Graphs
• Infinite games on finitely coloured graphs with applications to automata on infinite trees
• On the complexity of counter reachability games

Cites work

• Computer Science Logic
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Decidability results for the boundedness problem
• Distance desert automata and the star height problem
• Improved limitedness theorems on finite automata with distance functions
• Limitedness theorem on finite automata with distance functions: An algebraic proof
• On semigroups of matrices over the tropical semiring
• Regular cost functions. I: Logic and algebra over words
• The Non-deterministic Mostowski Hierarchy and Distance-Parity Automata
• Two-way cost automata and cost logics over infinite trees
• Weak alternating automata are not that weak
• Weak cost monadic logic over infinite trees

Cited in

(5)

• Games with bound guess actions
• Games where you can play optimally with arena-independent finite memory
• Quantifying Bounds in Strategy Logic
• scientific article; zbMATH DE number 7559480 (Why is no real title available?)
• Two-player boundedness counter games

This page was built for publication: Trading bounds for memory in games with counters

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3449476)