Space Complexity for Recognizing Connectedness of Three-Dimensional Patterns

Kenichi MORITA
Kazuhiro SUGATA

IEICE TRANSACTIONS (1976-1990)   Vol.E64    No.12    pp.778-785
Publication Date: 1981/12/25
Online ISSN: 
Print ISSN: 0000-0000
Type of Manuscript: PAPER
Category: Automata and Languages

Full Text: PDF(638.4KB)>>
Buy this Article

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.