Name
Title | ||
|---|---|---|
Closure Property Of Space-Bounded Two-Dimensional Alternating Turing Machines, Pushdown Automata, And Counter Automata |
Abstract | ||
|---|---|---|
This paper investigates closure property of the classes of sets accepted by space-bounded two-dimensional alternating Turing machines (2-atm's) and space-bounded two-dimensional alternating pushdown automata (2-apda's), and space-bounded two-dimensional alternating counter automata (2-aca's). Let L(m, n) : N-2-->N (N denotes the set of all positive integers) be a function with two variables m (= the number of rows of input tapes) and n (= the number of columns of input tapes). We show that(i) for any function f(m) = o(log m) (resp. f(m) = o(log m/log log m)) and any monotonic nondecreasing function g(n) space-constructible by a two-dimensional Turing machine (2-Tm) (resp. two-dimensional pushdown automaton (2-pda)), the class of sets accepted by L(rn, n) space-bounded 2-atm's (2-apda's) is not closed under row catenation, row + or projection, and(ii) for any function f(m) = o(m/log m) (resp. for any function f(m) such that log f(m) = o(log m)) and any monotonic nondecreasing function g(n) space-constructible by a two-dimensional counter automaton (2-ca), the class of sets accepted by L(m,n) space-bounded 2-aca's is not closed under row catenation, row + or projection,where L (m, n) = f (m) + g (n) (resp, L (m, n) = f (m) x g (n)). |
Year | DOI | Venue |
|---|---|---|
2001 | 10.1142/S0218001401001398 | INTERNATIONAL JOURNAL OF PATTERN RECOGNITION AND ARTIFICIAL INTELLIGENCE |
Keywords | Field | DocType |
two-dimensional alternating Turing machine, two-dimensional alternating, pushdown automaton, two-dimensional alternating counter automaton, closure property, space-bounded computation | Row,Integer,Discrete mathematics,Monotonic function,Combinatorics,Closure (mathematics),Counter automaton,Turing machine,Pushdown automaton,Mathematics,Bounded function | Journal |
Volume | Issue | ISSN |
15 | 7 | 0218-0014 |
Citations | PageRank | References |
2 | 0.44 | 7 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tokio Okazaki | 1 | 16 | 3.59 |
| Katsushi Inoue | 2 | 515 | 74.43 |
| Akira Ito | 3 | 71 | 18.13 |
| Yue Wang | 4 | 34 | 9.08 |