On communication-bounded synchronized alternating finite automata
type: Item
instance of: scholarly article
title: On communication-bounded synchronized alternating finite automata
zbMATH Open document ID: 0818.68071
DOI: 10.1007/BF01178509
author: Oscar H. Ibarra
author: Nicholas Q. Tran
published in: Acta Informatica
publication date: 1995-08-17T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 694997
zbMATH Keywords: synchronized alternating finite automata
MaRDI profile type: Publication
cites work: Q3975141
cites work: ON THE POWER OF ONE-WAY SYNCHRONIZED ALTERNATING MACHINES WITH SMALL SPACE
cites work: On the power of synchronization in parallel computations
cites work: On space-bounded synchronized alternating Turing machines
cites work: Synchronized finite automata and 2DFA reductions
cites work: Alternating multihead finite automata
description: scientific article; zbMATH DE number 694997