It cannot be decided whether a one-counter automaton accepts each string in its language using a counter whose value is bounded, with respect to the length of the input, by a constant. Furthermore, when the counter is bounded by a constant, its value cannot be limited by any recursive function in the size of the machine. By taking into account the costs of all computations ( strong measure) or of all accepting computations ( accept measure) instead of those of the least expensive accepting computations ( weak measure), the above-mentioned problem becomes decidable for both pushdown automata and one-counter automata, while the bounds for the pushdown height or the value of the counter, when non constant, are recursive in the size of the machine. We also prove that, under the weak measure, if a one-counter automaton accepts with a counter that, with respect to the input length, is not bounded by any constants, then the counter grows at least as a logarithmic function. This is in contrast with the case of pushdown automata in which the bound is a double-logarithmic function. For the strong and accept measures these bounds are shown to be linear, for both pushdown and one-counter automata.

Abstract The descriptional complexity of basic operations on regular languages using 1-limited automata, a restricted version of one-tape Turing machines, is investigated. When simulating operations on deterministic finite automata with deterministic 1-limited automata, the sizes of the resulting devices are polynomial in the sizes of the simulated machines. The situation is different when the operations are applied to deterministic 1-limited automata: while for boolean operations the simulations remain polynomial, for product, star, and reversal they cost exponential in size. The costs for product and star do not reduce if the given machines are sweeping two-way deterministic finite automata. These bounds are tight.

Abstract It cannot be decided whether a pushdown automaton accepts using a pushdown height, which does not depend on the input length, i.e., when it accepts using constant height. Furthermore, when a pushdown automaton accepts in constant height, the height can be arbitrarily large with respect to the size of the description of the machine, namely it does not exist any recursive function in the size of the description of the machine bounding the height of the pushdown. In contrast, in the restricted case of pushdown automata over a one-letter input alphabet, i.e., unary pushdown automata, the situation is different. First, acceptance in constant height is decidable. Moreover, in the case of acceptance in constant height, the height is at most exponential with respect to the size of the description of the pushdown automaton. We also prove a matching lower bound. Finally, if a unary pushdown automaton uses nonconstant height to accept, then the height should grow at least as the logarithm of the input length. This bound is optimal.

It is well known that one-tape Turing machines running in linear time are no more powerful than finite automata; namely they recognize exactly the class of regular languages. We prove that it is not decidable if a one-tape machine runs in linear time, even if it is deterministic and restricted to use only the portion of the tape that initially contains the input. This motivates the introduction of a constructive variant of one-tape machines, called a weight-reducing machine, and the investigation of its properties. We focus on the deterministic case. In particular, we show that, paying a polynomial size increase only, each weight-reducing machine can be turned into a halting one that runs in linear time. Furthermore each weight-reducing machine can be converted into equivalent nondeterministic and deterministic finite automata by paying an exponential and doubly-exponential increase in size, respectively. These costs cannot be reduced in the worst case.

Non-self-embedding grammars are a subclass of context-free grammars which only generate regular languages. The size costs of the conversion of non-self-embedding grammars into equivalent finite automata are studied, by proving optimal bounds for the number of states of nondeterministic and deterministic automata equivalent to given non-self-embedding grammars. In particular, each non-self-embedding grammar of size s can be converted into an equivalent nondeterministic automaton which has an exponential size in s and into an equivalent deterministic automaton which has a double exponential size in s. These costs are shown to be optimal. Moreover, they do not change if the larger class of quasi-non-self-embedding grammars, which still generate only regular languages, is considered. In the case of letter bounded languages, the cost of the conversion of non-self-embedding grammars and quasi-non-self-embedding grammars into deterministic automata reduces to an exponential of a polynomial in s.

Limited automata are one-tape Turing machines which are allowed to rewrite each tape cell only in the first d visits, for a given constant d. When d ≥ 2, these devices characterize the class of context-free languages. In this paper we consider restricted versions of these models which we call stron gly limited automata, where rewrites, head reversals, and state changes are allowed only at certain points of the computation. Those restrictions are inspired by a simple algorithm for accepting Dyck languages on 2-limited automata. We prove that the models so defined are still able to recognize all context-free languages. We also consider descriptional complexity aspects. We prove that there are polynomial transformations of context-free grammars and pushdown automata into strongly limited automata and vice versa.

Limited automata are one-tape Turing machines which are allowed to rewrite each tape cell only in the first d visits, for a given constant d. For each d ≥ 2, these devices characterize the class of context-free languages. We investigate the equivalen

The notion of two-way automata was introduced at the very beginning of automata theory. In 1959, Rabin and Scott and, independently, Shepherdson, proved that these models, both in the deterministic and in the nondeterministic versions, have the same

We investigate and compare the descriptional power of unary probabilistic and nondeterministic automata (pfa's and nfa's, respectively). We show the existence of a family of languages hard for pfa's in the following sense: For any positive integer d, there exists a unary d-cyclic language such that any pfa accepting it requires d states, as the smallest deterministic automaton. On the other hand, we prove that there exist infinitely many languages having pfa's which from one side do not match a known optimal state lower bound and, on the other side, they are smaller than nfa's which, in turn, are smaller than deterministic automata.

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 consider the problem of computing the costs---{ in terms of states---of optimal simulations between different kinds of finite automata recognizing unary languages. Our main result is a tight simulation of unary n-state two-way nondeterministic automata by $O({{\rm e}^{\sqrt{{n}\ln{n}}}})$-state one-way deterministic automata. In addition, we show that, given a unary n-state two-way nondeterministic automaton, one can construct an equivalent O(n 2 )-state two-way nondeterministic automaton performing both input head reversals and nondeterministic choices only at the ends of the input tape. Further results on simulating unary one-way alternating finite automata are also discussed.

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.