For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
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
Publication Date: 2014/06/01
Online ISSN: 1745-1337
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)>>
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)] ≠ ∅.