On communication-bounded synchronized alternating finite automata (Q1338889): Difference between revisions
From MaRDI portal
Changed an Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(One intermediate revision by one other user not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3975141 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: ON THE POWER OF ONE-WAY SYNCHRONIZED ALTERNATING MACHINES WITH SMALL SPACE / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the power of synchronization in parallel computations / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On space-bounded synchronized alternating Turing machines / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Synchronized finite automata and 2DFA reductions / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Alternating multihead finite automata / rank | |||
Normal rank |
Latest revision as of 10:30, 23 May 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