On communication-bounded synchronized alternating finite automata (Q1338889): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 03:59, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On communication-bounded synchronized alternating finite automata |
scientific article |
Statements
On communication-bounded synchronized alternating finite automata (English)
0 references
17 August 1995
0 references
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.
0 references
synchronized alternating finite automata
0 references