Affiliations: Department of Computer Science, P. J. Šafárik University, Jesenná 5, 04154 Košice, Slovakia. [email protected], [email protected]
Correspondence:
[†]
Address for correspondence: Department of Computer Science, P. J. Šafárik University, Jesenná 5, 04154 Košice, Slovakia
Note: [*] Supported by the Slovak Grant Agency for Science (VEGA) under contract 1/0177/21 “Descriptional and Computational Complexity of Automata and Algorithms” and by the Slovak Research and Development Agency under contract APVV-15-0091 “Efficient Algorithms, Automata, and Data Structures”.
Abstract: We show that, for automata using a finite number of counters, the minimal space that is required for accepting a nonregular language is (log n)ɛ. This is required for weak space bounds on the size of their counters, for real-time and one-way, and for nondeterministic and alternating versions of these automata. The same holds for two-way automata, independent of whether they work with strong or weak space bounds, and of whether they are deterministic, nondeterministic, or alternating. (Here ɛ denotes an arbitrarily small—but fixed—constant; the “space” refers to the values stored in the counters, rather than to the lengths of their binary representation.) On the other hand, we show that the minimal space required for accepting a nonregular language is nɛ for multicounter automata with strong space bounds, both for real-time and one-way versions, independent of whether they are deterministic, nondeterministic, or alternating, and also for real-time and one-way deterministic multicounter automata with weak space bounds. All these bounds are optimal both for unary and general nonregular languages. However, for automata equipped with only one counter, it was known that one-way nondeterministic automata cannot recognize any unary nonregular languages at all, even if the size of the counter is not restricted, while, with weak space bound log n, we present a real-time nondeterministic automaton recognizing a binary nonregular language here.
Keywords: space complexity, pushdown automata, counter automata, real-time automata
