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.

We show that, for any ϵ > 0, there exists a language accepted in strong ϵ log n space by a 2-way deterministic Turing machine working with a single binary worktape, that cannot be accepted in sublogarithmic weak space by any pebble machine (i.e.,

We present the first in-place algorithm for sorting an array of size n that performs, in the worst case, at most O ( n log n ) element comparisons and O ( n ) element transports.This solves a long-standing open problem, stated explicitly, for example, in Munro and Raman [1992], of whether there exists a sorting algorithm that matches the asymptotic lower bounds on all computational resources simultaneously.

We present the first in-place algorithm for sorting an array of size n that performs, in the worst case, at most O(n log n) element comparisons and O(n) element transports. This solves a long-standing open problem, stated explicitly, e.g., in J.I. Munro and V. Raman (1992), of whether there exists a sorting algorithm that matches the asymptotic lower bounds on all computational resources simultaneously.

The complexity measure under consideration is $\mbox{\rm SPACE}\!\times\!\mbox{\rm REVERSALS}$ for Turing machines that are able to branch both existentially and universally. We show that, for any function $h(n)$ between $\log\log n$ and $\log n$, $\Pi_1 \mbox{\rm SPACE}\!\times\!\mbox{\rm REVERSALS} (h(n))$ is separated {}from $\Sigma_1 \mbox{\rm SPACE}\!\times\!\mbox{\rm REVERSALS} (h(n))$ as well as {}from $\mbox{\sf co}\Sigma_1 \mbox{\rm SPACE}\!\times\!\mbox{\rm REVERSALS} (h(n))$, for middle, accept, and weak modes of this complexity measure. This also separates determinism from the higher levels of the alternating hierarchy. For "well-behaved" functions h(n) between log log n and log n, almost all of the above separations can be obtained by using unary witness languages. In addition, the construction of separating languages contributes to the research on minimal resource requirements for computational devices capable of recognizing nonregular languages. For any (arbitrarily slow growing) unbounded monotone recursive function f(n), a nonregular unary language is presented that can be accepted by a \middle\ \mbox{$\Pi_1$ alternating} Turing machine in s(n) space and i(n) input head reversals, with $s(n)\cdot i(n)\in{\cal O}(\log\log n\cdot f(n))$. Thus, there is no exponential gap for the optimal lower bound on the product $s(n)\cdot i(n)$ between unary and general nonregular language acceptance---in sharp contrast with the one-way case.

It is shown that for each $s(n)$-space-bounded nondeterministic Turing machine recognizing a language $L \subseteq 1^ * $ there exists an equivalent deterministic $O(s^2 (n))$-space-bounded machine, and also a nondeterministic $O(s(n))$-space-bounded machine recognizing the complement of L, for any $s(n)$, independent of whether $s(n)$ is below $\log (n)$ or is space constructible. In other words, the Savitch [J. Comput. System Sci., 4(1970), pp. 177–192] and Immerman–Szelepcsényi [SIAM J. Comput., 17(1988), pp. 935–938], [Acts Inform., 26(1988), pp. 279–284] theorems can be extended to any space bound $s(n)$ for languages over a single-letter alphabet.

The open problem of nondeterministic space constructibility for sublogarithmic functions is resolved. It is shown that there are no unbounded monotone increasing nondeterministically space constructible functions such that $\sup _{n \to \infty } s(n) / \log (n) = 0$. Consequently, space constructibility of monotone functionscannot be used to separate nondeterministic space from deterministic space, even for a very low-level complexity range, since functions like $\log \log (n)$ and ,$\sqrt {\log (n)} $ are not space constructible by nondeterministic Turing machines. This result is obtained by the extension of the $n \to n + n!$ method, described in [Hierarchies of memory limited computations, IEEE Conference Record on Switching Circuit Theory and Logical Design, 1965, pp. 179–190], to the nondeterministic case.