On communication-bounded synchronized alternating finite automata (Q1338889)

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 \(\Omega (\log \log n)\) communication symbols infinitely often; furthermore, a synchronized alternating finite automaton without nondeterminism (SUFA) needs to generate at least \(\Omega ({\root k \of {n}})\) communication symbols infinitely often for some constant \(k \geq 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, \(\text{NP} = \cup_{k \geq 1} {\mathcal 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.