Complementing two-way finite automata

We 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(n⁸)-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(n⁸) states.     

Multihead two-way probabilistic finite automata

We present properties of multihead two-way probabilistic finite automata that parallel those of their deterministic and nondeterministic counterparts. We define multihead probabilistic finite automata withlogspace constructible transition probabilities, and we describe a technique to simulate these automata by standard logspace probabilistic Turing machines. Next, we represent logspace probabilistic complexity classes as proper hierarchies based on corresponding multihead two-way probabilistic finite automata, and we show their (deterministic logspace) reducibility to the second levels of these hierarchies. We obtain a simple formula for the maximum inherent bandwidth of the configuration transition matrices associated with thek-head probabilistic finite automata processing a length-n input string. (The inherent bandwidth of the configuration transition matrices associated with an automaton processing a length-n input string is the smallest bandwidth we can get by changing the enumeration order of the automaton’s configurations.) Partially based on this relation, we find an apparently easier logspace complete problem forPL (the class of languages recognized by logspace unbounded-error probabilistic Turing machines), and we discuss possibilities for a space-efficient deterministic simulation of probabilistic automata.     

Alternating finite automata on ω-words

Alternating finite automata on ω-words are introduced as an extension of nondeterministic finite automata which process infinite sequences of symbols. The classes of ω-languages defined by alternating finite automata are investigated and characterized under four types of acceptance conditions. It is shown that for one type of acceptance condition alternation increases the power in comparison with nondeterminism and for other three acceptance conditions nondeterministic finite automata on ω-words have the same power as alternating ones.     

A note on one-way and two-way automata

The purpose of this note is to show that there exist non-regular languages whose memory requirements for recognition by one-way and two-way automata differ by a double exponential and that this difference cannot be exceeded.     

Language recognition by two-way deterministic pushdown automata

It is proved that any bounded context-free language can be recognized by a two-way deterministic automaton with a finite-rotary counter.Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 177–181, November–December 2004.This revised version was published online in April 2005 with a corrected cover date.     

Deterministic two-way one-head pushdown automata are very powerful

We show that if a language over a two-letter alphabet belongs to $\text{P}$, then its unary encoding belongs to 2DPDA(1).     

Some algebraic properties of measure-once two-way quantum finite automata

Quantum finite automata (QFA) can be divided into four kinds depend upon the head-directions and the measure times. They are measure-once one way QFA (MO-1QFA) introduced by Moore and Crutchfield (Theor Comput Sci 237: 275–306, 2000); measure-many one way QFA (MM-1QFA) and measure-many two-way QFA (MM-2QFA) introduced by Kondacs and Watrous (Proceedings of the 38th IEEE annual symposium on 433 foundations of computer science, 66–75, 1997); and measure-once two-way QFA (MO-2QFA) which were not given until now. The purpose of this work is mainly to discuss one kind of QFA, which is called MO-2QFA for brief. First of all, the definition of MO-2QFA is given and the conditions for preserving unitary properties are shown. Then, we analysis the basic algebraic properties of the class of languages which can be recognized by MO-2QFA, such as the union, intersection, complement and reversal operations. As well, we consider the catenation operation on the class of quantum languages recognized by MO-2QFA is closed in the generalized conditions.      

On the power of real-time two-way multihead finite automata with jumps

We investigate the relative power of jumps, nondeterminism, and number of heads for real-time automata. Results include showing that jumps and power that cannot be compensated for by nondeterminism and more heads. We also show that k+1 heads are more powerful than k heads, even if the finite automaton is allowed head to head jumps.