Paper Info
Title
Cooperating Systems Of 3-Way, 2-Dimensional Finite Automata
Abstract
This paper introduces a cooperating system of three-way, two-dimensional finite automata (CS-TR2-FA) which is a restricted version of a cooperating system of fourway, two-dimensional finite automata (CS-2-FA), and mainly investigates several fundamental properties of this system as a two-dimensional language acceptor whose input tapes are restricted to square ones. We show that(1) CS-TR2-FA's are equivalent in accepting power to three-way, two-dimensional simple multihead finite automata,(2) CS-2-FA's are more powerful than CS-TR2-FA's,(3) pound[CS-TR2-DFA(k)(S)] not subset of or equal to pound[CS-TR2-NFA(k)(S)],(4) U-1 less than or equal to k < infinity pound[CS-TR2-DFA(k)(S)] not subset of or equal to U-1 less than or equal to k < infinity pound[CS-TR2-NFA(k)(S)], and(5) pound[CS-TR2-DFA(k)(S)] (pound[CS-TR2-NFA(k)(S)]) not subset of or equal to pound[CS-TR2-DFA(k + 1)(S)] (pound[CS-TR2-NFA(k + 1)(S)]),where pound[CS-TR2-DFA(k)(S)] (pound[CS-TR2-NFA(k)(S)]) denotes the class of sets of square input tapes accepted by CS-TR2-FA's which consist of k deterministic (non-deterministic) finite automata.
Year
DOI
Venue
1995
10.1142/S021800149500033X
INTERNATIONAL JOURNAL OF PATTERN RECOGNITION AND ARTIFICIAL INTELLIGENCE
Keywords
Field
DocType
2-DIMENSIONAL FINITE AUTOMATON, COOPERATING SYSTEM, COMPLEXITY
Discrete mathematics,Deterministic automaton,Pattern recognition,Automated theorem proving,Theoretical computer science,Finite-state machine,Artificial intelligence,Time complexity,Mathematics,Computational complexity theory
Journal
Volume
Issue
ISSN
9
5
0218-0014
Citations 
PageRank 
References 
0
0.34
0
Authors
3
Name
Order
Citations
PageRank
Yue Wang1349.08
Katsushi Inoue251574.43
Itsuo Takanami337953.99