On the power of input-synchronized alternating finite automata

In this paper, we introduce a new model of automata, called input-synchronized alternating finite automata (i-SAFAs), and study the power of i-SAFAs. We here consider two types of i-SAFAs, one-way i-SAFAs and two-way i-SAFAs. Then we show that (1) the class of languages accepted by one-way i-SAFAs is equal to the class of regular languages, (2) two-way i-SAFAs are more powerful than one-way i-SAFAs, that is, there exists a language L such that L is accepted by a two-way i-SAFA but not accepted by any one-way i-SAFAs. In addition, we show that the class of languages accepted by f (n) parallel-bounded two-way i-SAFAs is included in Nspace(S(n)), where S(n) min{n log n, f (n) log n}.