The Variable Precision Rough Set Inductive Logic Programming model (VPRSILP model) extends the Variable Precision Rough Set (VPRS) model to Inductive Logic Programming (ILP). The generic Rough Set Inductive Logic Programming (gRS‐ILP) model provides a framework for ILP when the setting is imprecise and any induced logic program will not be able to distinguish between certain positive and negative examples. The gRS‐ILP model is extended in this paper to the VPRSILP model by including features of the VPRS model. The VPRSILP model is applied to strings and an illustrative experiment on transmembrane domains in amino acid sequences is presented.

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)).

The investigation of the computational power of randomized computations is one of the central tasks of current complexity and algorithm theory. In this paper for the first time a "strong" separation between the power of determinism, Las Vegas randomization, and nondeterminism for a computing model is proved. The computing models considered here are finite automata with two-dimensional input tapes (i.e., finite automata recognizing picture languages).

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.

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 four- way, 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) £[CS-TR2-DFA(k)S] ⊊ £[CS-TR2-NFA(k)S], (4) ⋃1≤k<∞ £[CS-TR2-DFA(k)S] ⊊ ⋃1≤k<∞ £[CS-TR2-NFA(k)S], and (5) £[CS-TR2-DFA(k)S] (£[CS-TR2-NFA(k)S]) ⊊ £[CS-TR2-DFA(k+1)S] (£[CS-TR2-NFA(k+1)S]), where £[CS-TR2-DFA(k)S] (£[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.

This paper first shows that REC, the family of recognizable picture languages in Giammarresi and Restivo,3 is equal to the family of picture languages accepted by two-dimensional on-line tessellation acceptors in Inoue and Nakamura.5 By using this result, we then solve open problems in Giammarresi and Restivo,3 and show that (i) REC is not closed under complementation, and (ii) REC properly contains the family of picture languages accepted by two-dimensional nondeterministic finite automata even over a one letter alphabet.

“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.

This paper deals with two topics concerning two-dimensional automata operating in parallel. We first investigate a relationship between the accepting powers of two-dimensional alternating finite automata (2-AFAs) and nondeterministic bottom-up pyramid cellular acceptors (NUPCAs), and show that Ω ( diameter × log diameter ) time is necessary for NUPCAs to simulate 2-AFAs. We then investigate space complexity of two-dimensional alternating Turing machines (2-ATMs) operating in small space, and show that if L (n) is a two-dimensionally space-constructible function such that lim n → ∞ L (n)/ loglog n > 1 and L (n) ≤ log n, and L′ (n) is a function satisfying L′ (n) =o (L(n)), 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 loglog n ≤ S (n) ≤ log n.

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.

This paper introduces a two-dimensional alternating Turing machine (2-ATM) which is an extension of an alternating Turing machine to two-dimensions. This paper also introduces a three-way two-dimensional alternating Turing machine (TR2-ATM) which is an alternating version of a three-way two-dimensional Turing machine. We first investigate a relationship between the accepting powers of space-bounded 2-ATM's (or TR2-ATM's) and ordinary space-bounded two-dimensional Turing machines (or three-way two-dimensional Turing machines). We then introduce a simple, natural complexity measure for 2-ATM's (or TR2-ATM's), called “leaf-size”, and provides a spectrum of complexity classes based on leaf-size bounded computations. We finally investigate the recognizability of connected patterns by 2-ATM's (or TR2-ATM's).