On communication-bounded synchronized alternating finite automata |
| |
Authors: | Oscar H Ibarra Nicholas Q Tran |
| |
Affiliation: | (1) Department of Computer Science, University of California, 93106 Santa Barbara, CA, USA |
| |
Abstract: | We continue the study of communication-bounded synchronized alternating finite automata (SAFA), first considered by Hromkovi et al. We show that to accept a nonregular language, an SAFA needs to generate at least (log logn) communication symbols infinitely often; furthermore, a synchronized alternating finite automaton without nondeterminism (SUFA) needs to generate at least (log logn) communication symbols infinitely often for some constantk 1. We also show that these bounds are tight.Next, we establish dense hierarchies of these machines on the function bounding the number of communication symbols. Finally, we give a characterization of NP in terms of communication-bounded multihead synchronized alternating finite automata, namely, NP =
k 1
L(SAFA(k-heads,n
k
-com)). This result recasts the relationships between P, NP, and PSPACE in terms of multihead synchronized alternating finite automata.Research supported in part by NSF Grant CCR89-18409 |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|