1,721,060 research outputs found
Testing the descriptional power of small Turing machines on nonregular language acceptance
No full textWe study lower bounds on space and input head reversals for deterministic, nondeterministic, and alternating Turing machines accepting nonregular languages. Three notions of space, namely strong, middle, weak are considered, and another notion, called accept, is introduced. In all cases, we obtain tight lower bounds. Moreover, we show that, while for determinism and nondeterminism such lower bounds are optimal even with respect to unary languages, for alternation optimal lower bounds for unary languages turn out to be strictly higher than those for languages over alphabets with two or more symbols
Optimal simulations between unary automata
Full text linkWe 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 -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
On space bounded Turing machines with a constant number of input head inversions
No full textIn this work we study classes of languages accepted by finitely ambiguous space bounded automata which are allowed to have an arbitrary constant number of input head inversions. In particular we show that: a) 1–way deterministic log–space bounded Turing machines are strictly less powerful than deterministic log–space bounded Turing machines with one input head inversion and, more generally, than 1–way unambiguous log–space bounded Turing machines, b) nondeterministic Turing machines with an arbitrary constant number of input head inversions can be simulated by 1–way nondeterministic Turing machines having the same space complexity and the same ambiguity degree. As a consequence of (b), we obtain that the census and ranking problems for the languages accepted in logarithmic space by finitely ambiguous Turing machines with an arbitrary constant number of input head inversions are NC1–reducible to the problem of computing the determinant of a n ⇥ n matrix of n–bit integers and hence solvable by a log–space uniform family of boolean circuits of polynomial size and depth O(log2 n)
Two-way automata simulations and unary languages
No full textOne of the main problems in automata theory is evaluating
the cost, in terms of states, of the optimal simulation of
two-way (or also one-way) nondeterministic by two-way
deterministic automata. The question, which was proposed in
1978 by {\sc W. Sakoda} and {\sc M. Sipser}, is still open.
In this paper, we aim to give some contributions to the
investigation of this problem. We show that in the
\emph{unary} case, namely for automata with a one-letter
input alphabet, the question can be restricted to studying
the cost of simulating \emph{quasi sweeping} two-way
nondeterministic automata accepting \emph{cyclic languages}
by two-way deterministic automata. Next, we prove a tight
lower bound on the number of states of two-way deterministic,
nondeterministic, and quasi sweeping automata accepting unary
languages. We also show that any one-way nondeterministic
automaton accepting a unary cyclic language can be simulated
by a two-way deterministic automaton without increasing the
number of states. This simulation, which is shown to be
optimal, improves the known quadratic simulation for unary
regular language
The descriptional power of sublogarithmic resource bounded Turing machines
No full textWe study lower bounds on space and input head reversals for deterministic, nondeterministic, and alternating Turing machines accepting nonregular languages. Three notions of space, namely strong, middle, weak, are considered and another notion, called accept, is introduced. In all cases we obtain tight lower bounds. Moreover, we show that, while for determinism and nondeterminism such lower bounds are optimal even with respect to unary languages, for alternation optimal lower bounds for unary languages turn out to be strictly higher than those for languages over alphabets with two or more symbols
The parallel complexity of deterministic and probabilistic automata
No full textA deterministic (probabilistic) automaton is said to be in TC0 whenever its transitions (stochastic event) can be computed by threshold circuits of polynomial size and constant depth. Here, we prove that: The class of deterministic automata in TC0 is closed under homomorphism, sub-automaton, and alpha0-product operations. The class of k-state deterministic (probabilistic) automata is contained in TC0 if and only if k les 4 (k les 2), unless TC0 = NC1. Moreover, the possibility of ranking regular languages in TC0 is related to the group-structure of their syntactic monoid
Unary automata simulations and cyclic languages
No full textA tight lower bound on the number of states of two–way deterministic and nondeterministic automata accepting unary languages is proved. This result represents a useful tool to study the cost — in terms of states — of the simulations of two–way automata with other kinds of automata and vice versa. We also show that any one–way nondeterministic automaton accepting a unary cyclic language can be
simulated by a two–way deterministic automaton without increasing the number of states. This improves the quadratic simulation known for unary languages. Furthermore, by using the above mentioned lower bound, we are able to show that our simulation is optimal
Optimal simulations between unary automata
No full textWe 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(e(root 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 at the endmarkers only. Further results on simulating unary alternating finite automata are pointed out. Our results give answers to some questions left open in the literature
Threshold circuits for some matrix operations : consequences on regular and probabilistic languages
No full text- …
