zbMATH — the first resource for mathematics

EXPSPACE-complete variant of countdown games, and simulation on succinct one-counter nets. (English) Zbl 06963050
Potapov, Igor (ed.) et al., Reachability problems. 12th international conference, RP 2018, Marseille, France, September 24–26, 2018. Proceedings. Cham: Springer (ISBN 978-3-030-00249-7/pbk; 978-3-030-00250-3/ebook). Lecture Notes in Computer Science 11123, 59-74 (2018).
Summary: We answer an open complexity question for simulation preorder of succinct one-counter nets (i.e., one-counter automata with no zero tests where counter increments and decrements are integers written in binary), by showing that all relations between bisimulation equivalence and simulation preorder are EXPSPACE-hard for these nets. We describe a reduction from reachability games whose EXPSPACE-completeness in the case of succinct one-counter nets was shown by Hunter [RP 2015], by using other results. We also provide a direct self-contained EXPSPACE-completeness proof for a special case of such reachability games, namely for a modification of countdown games that were shown EXPTIME-complete by Jurdzinski, Sproston, Laroussinie (LMCS 2008); in our modification the initial counter value is not given but is freely chosen by the first player.
For the entire collection see [Zbl 1396.68021].
68Qxx Theory of computing
Full Text: DOI