A Note on Cooperating Systems of One-Way Alternating Finite Automata with Only Universal States
Summary :
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)] ≠ ∅.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E97-A No.6 pp.1375-1377
- Publication Date
- 2014/06/01
- Publicized
- 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)
- Category
Authors
Tatsuya FUJIMOTO
Tokuyama College of Technology
Tsunehiro YOSHINAGA
Tokuyama College of Technology
Makoto SAKAMOTO
University of Miyazaki
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Tatsuya FUJIMOTO, Tsunehiro YOSHINAGA, Makoto SAKAMOTO, "A Note on Cooperating Systems of One-Way Alternating Finite Automata with Only Universal States" in IEICE TRANSACTIONS on Fundamentals,
vol. E97-A, no. 6, pp. 1375-1377, June 2014, doi: 10.1587/transfun.E97.A.1375.
Abstract: 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)] ≠ ∅.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E97.A.1375/_p
Copy
@ARTICLE{e97-a_6_1375,
author={Tatsuya FUJIMOTO, Tsunehiro YOSHINAGA, Makoto SAKAMOTO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A Note on Cooperating Systems of One-Way Alternating Finite Automata with Only Universal States},
year={2014},
volume={E97-A},
number={6},
pages={1375-1377},
abstract={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)] ≠ ∅.},
keywords={},
doi={10.1587/transfun.E97.A.1375},
ISSN={1745-1337},
month={June},}
Copy
TY - JOUR
TI - A Note on Cooperating Systems of One-Way Alternating Finite Automata with Only Universal States
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1375
EP - 1377
AU - Tatsuya FUJIMOTO
AU - Tsunehiro YOSHINAGA
AU - Makoto SAKAMOTO
PY - 2014
DO - 10.1587/transfun.E97.A.1375
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E97-A
IS - 6
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - June 2014
AB - 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)] ≠ ∅.
ER -
English
