A Note on Cooperating Systems of One-Way Alternating Finite Automata with Only Universal States

Tatsuya FUJIMOTO  Tsunehiro YOSHINAGA  Makoto SAKAMOTO  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E97-A   No.6   pp.1375-1377
Publication Date: 2014/06/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E97.A.1375
Type of Manuscript: Special Section LETTER (Special Section on Discrete Mathematics and Its Applications)
cooperating system of one-way finite automata,  alternating finite automata,  universal states,  computational complexity,  

Full Text: PDF(79.7KB)>>
Buy this Article

A cooperating system of finite automata (CS-FA) has more than one finite automata (FA's) and an input tape. These FA's operate independently on the input tape and can communicate with each other on the same cell of the input tape. For each k ≥ 1, let L[CS-1DFA(k)] (L[CS-1UFA(k)]) be the class of sets accepted by CS-FA's with k one-way deterministic finite automata (alternating finite automata with only universal states). We show that L[CS-1DFA(k+1)] - L[CS-1UFA(k)] ≠ ∅ and L[CS-1UFA(2)] - ∪1≤k<∞L[CS-1DFA(k)] ≠ ∅.