@inproceedings{10.1007/978-3-030-00250-3_5,
    Abstract = {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.},
    Address = {Cham},
    Author = {Jan{\v{c}}ar, Petr and Osi{\v{c}}ka, Petr and Sawa, Zden{\v{e}}k},
    BookTitle = {Reachability Problems},
    Editor = {Potapov, Igor and Reynier, Pierre-Alain},
    File = {Jančar2018\_Chapter\_EXPSPACE-CompleteVariantOfCoun (0) - a - a - a.pdf},
    ISBN = {978-3-030-00250-3},
    Pages = {59--74},
    Publisher = {Springer International Publishing},
    Title = {EXPSPACE-Complete Variant of Countdown Games, and Simulation on Succinct One-Counter Nets},
    Year = {2018},
    date-added = {2019-02-12 09:56:34 +0100},
    date-modified = {2019-02-12 09:56:34 +0100},
    doi = {10.1007/978-3-030-00250-3_5}
}

@inproceedings{10.1007/978-3-030-00250-3_5, Abstract = {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.}, Address = {Cham}, Author = {Jan{\v{c}}ar, Petr and Osi{\v{c}}ka, Petr and Sawa, Zden{\v{e}}k}, BookTitle = {Reachability Problems}, Editor = {Potapov, Igor and Reynier, Pierre-Alain}, File = {Jančar2018_Chapter_EXPSPACE-CompleteVariantOfCoun (0) - a - a - a.pdf}, ISBN = {978-3-030-00250-3}, Pages = {59--74}, Publisher = {Springer International Publishing}, Title = {EXPSPACE-Complete Variant of Countdown Games, and Simulation on Succinct One-Counter Nets}, Year = {2018}, date-added = {2019-02-12 09:56:34 +0100}, date-modified = {2019-02-12 09:56:34 +0100}, doi = {10.1007/978-3-030-00250-3_5} }