1,720,988 research outputs found
Pairs of complementary unary languages with “balanced” nondeterministic automata
No full textFor each sufficiently large n, there exists a unary regular language L such that both L and its complement L c are accepted by unambiguous nondeterministic automata with at most n states, while the smallest deterministic automata for these two languages still require a superpolynomial number of states, at least e^{\Omega(\sqrt[3]{n\cdot\ln^{2}\n})} . Actually, L and L c are “balanced” not only in the number of states but, moreover, they are accepted by nondeterministic machines sharing the same transition graph, differing only in the distribution of their final states. As a consequence, the gap between the sizes of unary unambiguous self-verifying automata and deterministic automata is also superpolynomial
Two-way automata making choices only at the endmarkers
No full textThe question of the state-size cost for simulation of two-way nondeterministic automata (2 nfas) by two-way deterministic automata (2 dfas) was raised in 1978 and, despite many attempts, it is still open. Subsequently, the problem was attacked by restricting the power of 2 dfas (e.g., using a restricted input head movement) to the degree for which it was already possible to derive some exponential gaps between the weaker model and the standard 2 nfas. Here we use an opposite approach, increasing the power of 2 dfas to the degree for which it is still possible to obtain a subexponential conversion from the stronger model to the standard 2 dfas. In particular, it turns out that subexponential conversion is possible for two-way automata that make nondeterministic choices only when the input head scans one of the input tape endmarkers. However, there is no restriction on the input head movement. This implies that an exponential gap between 2 nfas and 2 dfas can be obtained only for unrestricted 2 nfas using capabilities beyond the proposed new model. As an additional bonus, conversion into a machine for the complement of the original language is polynomial in this model. The same holds for making such machines self-verifying, halting, or unambiguous. Finally, any superpolynomial lower bound for the simulation of such machines by standard 2 dfas would imply L ≠ NL. In the same way, the alternating version of these machines is related to L over(=, ?) NL over(=, ?) P, the classical computational complexity problems. © 2014 Elsevier Inc. All rights reserved
One pebble versus ε · log n bits [One pebble versus epsilon.log n bits]
No full textWe 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., a 2-way nondeterministic Turing machine with one pebble that can be moved onto the input cells). Moreover, we provide optimal unary lower bounds on the product of space and input head reversals for strong and weak pebble machines accepting nonregular languages
Sublogarithmic bounds on space and reversals
Full text linkThe complexity measure under consideration is SPACE x 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) SPACE x REVERSALS(h(n)) is separated from Sigma(1)SPACE x REVERSALS(h(n)) as well as from co Sigma(1)SPACE x 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 Pi(1) alternating Turing machine in s(n) space and i(n) input head reversals, with s(n) . i(n) is an element of O(log log n . f(n)). Thus, there is no exponential gap for the optimal lower bound on the product s(n) . i(n) between unary and general nonregular language acceptance-in sharp contrast with the one-way case
Pairs of Complementary Unary Languages with "Balanced" Nondeterministic Automata
No full textFor each sufficiently large N, there exists a unary regular language L such that both L and its complement L^c are accepted by unambiguous nondeterministic automata with at most N states while the smallest deterministic automata for these two languages require a superpolynomial number of states, at least . Actually, L and L^c are accepted by nondeterministic machines sharing the same transition graph, differing only in the distribution of their final states. As a consequence, the gap between the sizes of unary unambiguous self-verifying automata and deterministic automata is also superpolynomial
Descriptional Complexity Issues Concerning Regular Languages
No full textIn the realm of descriptional complexity, systems are compared on the basis of their size. Here, we consider two formalisms for representing regular languages: constant height pushdown automata and straight line programs for regular expressions. We show that their sizes are polynomially related. Comparing them with the sizes of finite state automata and regular expressions, we obtain optimal exponential and double exponential gaps, i.e., a more concise representation of regular languages
Removing nondeterminism in constant height pushdown automata
No full textWe study the descriptional cost of removing nondeterminism in constant height pushdown automata - i.e., pushdown automata with a built-in constant limit on the height of the pushdown. We show a double-exponential size increase when converting a constant height nondeterministic pushdown automaton into an equivalent deterministic device. Moreover, we prove that such a double-exponential blow-up cannot be avoided by certifying its optimality. As a direct consequence, we get that eliminating nondeterminism in classical finite state automata is single-exponential even with the help of a constant height pushdown store
More concise representation of regular languages by automata and regular expressions
No full textWe consider two formalisms for representing regular languages: constant height pushdown automata and straight line programs for regular expressions. We constructively prove that their sizes are polynomially related. Comparing them with the sizes of finite state automata and regular expressions, we obtain optimal exponential and double exponential gaps, i.e., a more concise representation of regular languages
One pebble versus log n bits
No full textWe show that pebble machines (i.e., 2-way nondeterministic Turing machines with one pebble that can be moved onto the input cells) working in sublogarithmic weak space are not able to simulate strong log-space bounded 2-way deterministic Turing machines. We prove this by exhibiting a witness language. Moreover, we provide an optimal lower bound on the product of space and input head reversals for pebble machines accepting nonregular languages
Complementing two-way finite automata
No full textAbstractWe study the relationship between the sizes of two-way finite automata accepting a language and its complement. In the deterministic case, for a given automaton (2dfa) with n states, we build an automaton accepting the complement with at most 4n states, independently of the size of the input alphabet. Actually, we show a stronger result, by presenting an equivalent 4n-state 2dfa that always halts. For the nondeterministic case, using a variant of inductive counting, we show that the complement of a unary language, accepted by an n-state two-way automaton (2nfa), can be accepted by an O(n8)-state 2nfa. Here we also make 2nfa’s halting. This allows the simulation of unary 2nfa’s by probabilistic Las Vegas two-way automata with O(n8) states
- …
