Countdown games, and simulation on (succinct) one-counter nets
share
We answer an open complexity question by Hofman, Lasota, Mayr, Totzke (LMCS 2016) [HLMT16] 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. We also present a new simplified proof of the belt theorem that gives a simple graphic presentation of simulation preorder on one-counter nets and leads to a polynomial-space algorithm; it is an alternative to the proof from [HLMT16].
READ FULL TEXT