For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Space Complexity for Recognizing Connectedness of Three-Dimensional Patterns
IEICE TRANSACTIONS (1976-1990)
Publication Date: 1981/12/25
Print ISSN: 0000-0000
Type of Manuscript: PAPER
Category: Automata and Languages
Full Text: PDF(638.4KB)>>
In this paper we study the problem of recognizing connectedness of three-dimensional patterns. We investigate the upper and lower bounds of space complexity for this problem. These results are compared with two-dimensional case. It reveals that recognizing three-dimensional connectedness is much more difficult than two-dimensional case. We introduce a three-dimensional k-marker automaton (MA(k)) and a three-dimensional S(n) space-bounded Turing machine (TM(S(n))). We prove that a nondeterministic MA(1), a nondeterministic TM(log n) and a deterministic TM((log n)2) can accept connected patterns. We also prove that a deterministic TM((log n)2) can accept patterns of k connected components (k is a constant). Next, a three-dimensional five-way S(n) space-bounded Turing machine (5WTM(S(n))) is introduced. It is a restricted model of TM(S(n)) whose input head can move north, south, east, west and down, but not up. We prove that the space n2 log n is necessary and sufficient amount for a deterministic 5WTM(S(n)) to recognize connected patterns.