A hierarchy that does not collapse : alternations in low level space
Normal forms for phrase-structure grammars
Factoring and testing primes in small space
We discuss how much space is sufficient to decide whether a unary given number is a prime. We show that (log log ) space is sufficient for a deterministic Turing machine, if it is equipped with an additional pebble movable along the input tape, and also for an alternating machine, if the space restriction applies only to its accepting computation subtrees. In other words, the language is a prime is in pebble–DSPACE(log log ) and also in accept–ASPACE(log log ). Moreover, if the given is composite,...
Translation from classical two-way automata to pebble two-way automata
We study the relation between the standard two-way automata and more powerful devices, namely, two-way finite automata equipped with some additional “pebbles” that are movable along the input tape, but their use is restricted (nested) in a stack-like fashion. Similarly as in the case of the classical two-way machines, it is not known whether there exists a polynomial trade-off, in the number of states, between the nondeterministic and deterministic two-way automata with nested pebbles. However,...
A space lower bound for acceptance by one-way -alternating machines
Translation from classical two-way automata to pebble two-way automata
We study the relation between the standard two-way automata and more powerful devices, namely, two-way finite automata equipped with some additional “pebbles” that are movable along the input tape, but their use is restricted (nested) in a stack-like fashion. Similarly as in the case of the classical two-way machines, it is not known whether there exists a polynomial trade-off, in the number of states, between the nondeterministic and deterministic two-way automata with nested pebbles. However,...
A Space Lower Bound for Acceptance by One-Way Π-Alternating Machines
We show that one-way Π-alternating Turing machines cannot accept unary nonregular languages in (log ) space. This holds for an mode of space complexity measure, defined as the worst cost of any accepting computation. This lower bound should be compared with the corresponding bound for one-way Σ-alternating machines, that are able to accept unary nonregular languages in space (log log ). Thus, Σ-alternation is more powerful than Π-alternation for space bounded one-way machines with unary inputs. ...
Conversion of regular expressions into realtime automata
We consider conversions of regular expressions into -realtime finite state automata, , automata in which the number of consecutive uses of -transitions, along any computation path, is bounded by a fixed constant . For -realtime automata, , for automata that cannot change the state, without reading an input symbol, more than two times in a row, we show that the conversion of a regular expression into such an automaton produces only states, log) -transitions, and alphabet-transitions. We also show...
Hyper-minimizing minimized deterministic finite state automata
We present the first (polynomial-time) algorithm for reducing a given deterministic finite state automaton (DFA) into a hyper-minimized DFA, which may have fewer states than the classically minimized DFA. The price we pay is that the language recognized by the new machine can differ from the original on a finite number of inputs. These hyper-minimized automata are optimal, in the sense that every DFA with fewer states must disagree on infinitely many inputs. With small modifications, the construction...
Hyper-minimizing minimized deterministic finite state automata
We present the first (polynomial-time) algorithm for reducing a given deterministic finite state automaton (DFA) into a DFA, which may have fewer states than the classically minimized DFA. The price we pay is that the language recognized by the new machine can differ from the original on a finite number of inputs. These hyper-minimized automata are optimal, in the sense that every DFA with fewer states must disagree on infinitely many inputs. With small modifications, the construction works also...
Page 1