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): N2 → 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(m,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 ) (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) × g(n)).

This paper introduces a three-way two-dimensional probabilistic Turing machine (tr2-ptm), and investigates several properties of the machine. The tr2-ptm is a two-dimensional probabilistic Turing machine (2-ptm) whose input head can only move left, right, or down, but not up. Let 2-ptm s (resp. tr2-ptm s ) denote a 2-ptm (resp. tr2-ptm) whose input tape is restricted to square ones, and let 2-PTM s (S(n)) (resp. TR2-PTM s (S(n))) denote the class of sets recognized by S(n) space-bounded 2-ptm s 's (resp. tr2-ptm s 's) with error probability less than ½, where S(n): N→N is a function of one variable n (= the side-length of input tapes). Let TR2-PTM(L(m,n)) denote the class of sets recognized by L(m,n) space-bounded tr2-ptm's with error probability less than ½, where L(m,n): N 2 →N is a function of two variables m (= the number of rows of input tapes) and n (= the number of columns of input tapes). The main results of this paper are: (1) 2-NFA s - TR2-PTM s (S(n))≠ϕ for any S(n)=o(log n), where 2-NFA s denotes the class of sets of square tapes accepted by two-dimensional nondeterministic finite automata, (2) TR2-PTM s S(n)[Formula: see text]2-PTM s (S(n)) for any S(n)=o(log n), and (3) for any function g(n)=o(log n) (resp. g(n)=o(log n/log log n)) and any monotonic nondecreasing function f(m) which can be constructed by some one-dimensional deterministic Turing machine, TR2-PTM(f(m)+g(n)) (resp. TR2-PTM(f(m)×g(n))) is not closed under column catenation, column closure, and projection. Additionally, we show that two-dimensional nondeterministic finite automata are equivalent to two-dimensional probabilistic finite automata with one-sided error in accepting power.

Given a binary image of square size, it is desirable to identify the amount of shift of the foreground pixels such that it minimizes the total number of leaves of the region quadtree that represents the image. This problem is called quadtree normalization. For this problem, the best known algorithms have time complexities O(N2 log N), where N is the side length of given images (so, N2 is the total number of pixels). In this paper, we show an algorithm that has the optimal complexity O(N2) for some class of images. Our strategy consists of two stages: decomposing the given image into axis-parallel rectangles at first and integrating the contributions of individual rectangles afterwards. To do this, we derive the necessary and sufficient condition on any decomposition scheme, in a conditional form of the well-known Inclusion–Exclusion Principle. It turns out that the generated primitives must be "strictly overlapped" to some extent. The optimal linear-time complexity can be achieved in the case when the total area of the decomposed rectangles is bounded by O(N2) e.g. for the class of images whose foreground part is drawn with the finite number of rectangles. We only sketch the outline of the first decomposition stage of the new algorithm, but the last integrating stage is described in details.

This paper investigates the space hierarchies of the language classes for two-dimensional Turing machines (2-TM's), two-dimensional pushdown automata (2-PDA's) and two-dimensional counter automata (2-CA's) with small space. We show that (1) if L(n) is space constructible by a 2-TM, L(n) ≤ log n and L′(n) = o(L(n)), then strong 2-DSPACE(L(n)) – weak 2-ASPACE(L′(n)) ≠ ∅, (2) if L(n) is space constructible by a 2-PDA, L(n) ≤ log n and L′(n) = o(L(n)), then strong 2-DPDA(L(n)) – weak 2-ASPACE(L′(n)) ≠ ∅, and (3) if L(n) is space-constructible by a 2-CA, L(n) ≤ n and L′(n) = o(L(n)), then strong 2-DCA(L(n)) – weak 2-ACA(L′(n)) ≠ ∅, (4) where strong 2-DSPACE(L(n)) (strong 2-DPDA(L(n)), strong 2-DCA(L(n))) denotes the class of sets accepted by strongly L(n) space-bounded deterministic 2-TM's (2-PDA's, 2-CA's), and weak 2-ASPACE(L′(n)) (weak 2-ACA(L′(n))) denotes the class of sets accepted by weakly L′(n) space-bounded alternating 2-TM's (2-CA's). We also investigate the closure property of space-bounded alternating 2-PDA's and 2-CA's under complementation, and show that (1) if L(n) = o( log log n), then the class of sets accepted by L(n) space-bounded alternating 2-PDA's is not closed under complementation, and (2) if L(n) is space-constructible by a 2-CA, L(n) ≤ n and [Formula: see text], then the class of sets accepted by L′(n) space-bounded alternating 2-CA's is not closed under complementation.

Several nonclosure properties of each class of sets accepted by two-dimensional alternating one-marker automata, alternating one-marker automata with only universal states, nondeterministic one-marker automata, deterministic one-marker automata, alternating finite automata, and alternating finite automata with only universal states are shown. To do this, we first establish the upper bounds of the working space used by "three-way" alternating Turing machines with only universal states to simulate those "four-way" non-storage machines. These bounds provide us a simplified and unified proof method for the whole variants of one-marker and/or alternating finite state machine, without directly analyzing the complex behavior of the individual four-way machine on two-dimensional rectangular input tapes. We also summarize the known closure properties including Boolean closures for all the variants of two-dimensional alternating one-marker automata.

Recently, related to the open problem of whether deterministic and nondeterministic space (especially lower-level) complexity classes are separated, the inkdot Turing machine was introduced. An inkdot machine is a conventional Turing machine capable of dropping an inkdot on a given input tape for a landmark, but not to pick it up nor further erase it. In this paper, we introduce a finite state version of the inkdot machine as a weak recognizer of the properties of digital pictures, rather than a Turing machine supplied with a one-dimensional working tape. We first investigate the sufficient spaces of three-way Turing machines to simulate two-dimensional inkdot finite automaton, as preliminary results. Next, we investigate the basic properties of two-dimensional inkdot automaton, i.e. the hierarchy based on the number of inkdots and the relationship of two-dimensional inkdot automata to other conventional two-dimensional automata. Finally, we investigate the recognizability of connected pictures of two-dimensional inkdot finite machines.

“Leaf-size” (or “branching”) is the minimum number of leaves of some accepting computation trees of alternating devices. For example, one leaf corresponds to nondeterministic computation. In this paper, we investigate the effect of constant leaves of two-dimensional alternating Turing machines, and show the following facts: (1) For any function L(m, n), k leaf- and L(m, n) space-bounded two-dimensional alternating Turing machines which have only universal states are equivalent to the same space bounded deterministic Turing machines for any integer k≥1, where m (n) is the number of rows (columns) of the rectangular input tapes. (2) For square input tapes, k+1 leaf- and o(log m) space-bounded two-dimensional alternating Turing machines are more powerful than k leaf-bounded ones for each k≥1. (3) The necessary and sufficient space for three-way deterministic Turing machines to simulate k leaf-bounded two-dimensional alternating finite automata is nk+1, where we restrict the space function of three-way deterministic Turing machines to depend only on the number of columns of the given input tapes.

We denote a two-dimensional deterministic (nondeterministic) one-marker automaton by 2-DM1 (2-NM1), and a three-way two-dimensional deterministic (nondeterministic) Turing machine by TR2-DTM (TR2-NTM). In this paper, we show that the necessary and sufficient space for TR2-NTMs to simulate 2-DM1s (2-NM1s) is n log n (n2), and the necessary and sufficient space for TR2-DTMs to simulate 2-DM1s (2-NM1s) is 2O(n log n) (2 O(n2)), where n is the number of columns of rectangular input tapes.