Name
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 Löding. 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. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1007/978-3-662-47666-6_16 | ICALP 2015 Proceedings, Part II, of the 42nd International Colloquium on Automata, Languages, and Programming - Volume 9135 |
Field | DocType | Volume |
Discrete mathematics,Combinatorics,Computer science,Regular language,Conjecture,Special case,Bounded function | Conference | abs/1709.03121 |
ISSN | Citations | PageRank |
0302-9743 | 0 | 0.34 |
References | Authors | |
12 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nathanaël Fijalkow | 1 | 61 | 19.71 |
| Florian Horn | 2 | 53 | 6.57 |
| Denis Kuperberg | 3 | 41 | 9.68 |
| Michal Skrzypczak | 4 | 23 | 11.34 |