Name
Abstract | ||
|---|---|---|
This paper deals with two topics concerning two-dimensional automata operating in parallel. We first investigate a relationship between the accepting powers of two-dimension al alternating finite automata (2-AFAs) and nondeterministic bottom-up pyramid cellular accep tors (NUPCAs), and show that II (diameter x log diameter) time is necessary for NUPCAs to simulate 2-AFAs. We then investigate space complexity of two-dimension al alternating Turing machines (2-ATMs) operating in small space, and show tlat if L(n) is a two-dimensionally space-comstructible function such that lim"__>coL(«)/loglogii > 1 and L(n) =s logn, and L'{ri) is a function satisfying L'(n) = o(L(/i)), then there exists a set accepted by some strongly L(n) space-bounded two-dimensional deterministic Turing machine, but not accepted by any weakly L'(n) space-bounded 2-ATM, and thus there exists a rich space hierarchy for weakly S(n) space-bounded 2-ATMs with loglogw ^ S(n) ^ logn. |
Year | DOI | Venue |
|---|---|---|
1992 | 10.1142/S0218001492000126 | IJPRAI |
Keywords | Field | DocType |
two-dimensional automata operating,complexity.,alternating turing machine,two-dimensional automata,pyramid cellular acceptor,col,turing machine,bottom up,satisfiability,space complexity,two dimensions,complexity,finite automata | Cellular automaton,Combinatorics,Nondeterministic algorithm,Automaton,Finite-state machine,Turing machine,Artificial intelligence,Alternating Turing machine,Non-deterministic Turing machine,Two-dimensional space,Machine learning,Mathematics | Journal |
Volume | Issue | ISBN |
6 | 2&3 | 981-02-1120-1 |
Citations | PageRank | References |
2 | 0.44 | 11 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Katsushi Inoue | 1 | 515 | 74.43 |
| Itsuo Sakuramoto | 2 | 2 | 0.44 |
| Makoto Sakamoto | 3 | 2 | 0.78 |
| Itsuo Takanami | 4 | 379 | 53.99 |