@article{BohmGollerJancar:Regularity:OCA:JCSS:2014,
    Abstract = {Abstract A one-counter automaton is a pushdown automaton with a singleton stack alphabet, where stack emptiness can be tested; it is a real-time automaton if it contains no ε-transitions. We study the computational complexity of the problems of equivalence and regularity (i.e. semantic finiteness) on real-time one-counter automata. The first main result shows \{PSPACE\} -completeness of bisimulation equivalence; this closes the complexity gap between decidability [23] and \{PSPACE\} -hardness [25]. The second main result shows \{NL\} -completeness of language equivalence of deterministic real-time one-counter automata; this improves the known \{PSPACE\} upper bound (indirectly shown by Valiant and Paterson [27]). Finally we prove P -completeness of the problem if a given one-counter automaton is bisimulation equivalent to a finite system, and \{NL\} -completeness of the problem if the language accepted by a given deterministic real-time one-counter automaton is regular.},
    Author = {B{\"o}hm, Stanislav and G{\"o}ller, Stefan and Jan{\v c}ar, Petr},
    File = {Bisimulation equivalence and regularity for real-time one-counter automata - Böhm, Göller, Jančar (0) (0) - a - a - a.pdf},
    ISSN = {0022-0000},
    Journal = {Journal of Computer and System Sciences},
    Keywords = {Regularity},
    Number = {4},
    Pages = {720 - 743},
    Title = {Bisimulation equivalence and regularity for real-time one-counter automata},
    URL = {http://www.sciencedirect.com/science/article/pii/S0022000013001906},
    Volume = {80},
    Year = {2014},
    bdsk-url-1 = {http://www.sciencedirect.com/science/article/pii/S0022000013001906},
    bdsk-url-2 = {http://dx.doi.org/10.1016/j.jcss.2013.11.003},
    date-added = {2016-09-12 13:59:03 +0000},
    date-modified = {2016-09-12 13:59:03 +0000},
    doi = {10.1016/j.jcss.2013.11.003}
}

@article{BohmGollerJancar:Regularity:OCA:JCSS:2014, Abstract = {Abstract A one-counter automaton is a pushdown automaton with a singleton stack alphabet, where stack emptiness can be tested; it is a real-time automaton if it contains no ε-transitions. We study the computational complexity of the problems of equivalence and regularity (i.e. semantic finiteness) on real-time one-counter automata. The first main result shows {PSPACE} -completeness of bisimulation equivalence; this closes the complexity gap between decidability [23] and {PSPACE} -hardness [25]. The second main result shows {NL} -completeness of language equivalence of deterministic real-time one-counter automata; this improves the known {PSPACE} upper bound (indirectly shown by Valiant and Paterson [27]). Finally we prove P -completeness of the problem if a given one-counter automaton is bisimulation equivalent to a finite system, and {NL} -completeness of the problem if the language accepted by a given deterministic real-time one-counter automaton is regular.}, Author = {B{\"o}hm, Stanislav and G{\"o}ller, Stefan and Jan{\v c}ar, Petr}, File = {Bisimulation equivalence and regularity for real-time one-counter automata - Böhm, Göller, Jančar (0) (0) - a - a - a.pdf}, ISSN = {0022-0000}, Journal = {Journal of Computer and System Sciences}, Keywords = {Regularity}, Number = {4}, Pages = {720 - 743}, Title = {Bisimulation equivalence and regularity for real-time one-counter automata}, URL = {http://www.sciencedirect.com/science/article/pii/S0022000013001906}, Volume = {80}, Year = {2014}, bdsk-url-1 = {http://www.sciencedirect.com/science/article/pii/S0022000013001906}, bdsk-url-2 = {http://dx.doi.org/10.1016/j.jcss.2013.11.003}, date-added = {2016-09-12 13:59:03 +0000}, date-modified = {2016-09-12 13:59:03 +0000}, doi = {10.1016/j.jcss.2013.11.003} }