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.

This paper presents a generating method of LSP parameter sequences for speech synthesis by rule. In our method, neural networks are schemed to generate LSP parameter sequences of Vowel-Consonant-Vowel (VCV) units. The quality of synthesized speech by concatenation way of VCV units through table-look-up technique can not be improved so much owing to the distortion appearing on VCV units junction. In our method, the neural networks concatenate VCV units step by step with less distortion on VCV units junction, which synthesizes good quality speech.

A noise reduction filter composed of a sandglass-type neural network (Sandglass-type Neural network Noise Reduction Filter: SNNRF) was proposed in the present paper. Sandglass-type neural network (SNN) has symmetrical layer construction, and consists of the same number of units in input and output layers and less number of units in a hidden layer. It is known that SNN has the property of processing signals which is equivalent to KL expansion after learning. We applied the recursive least square (RLS) method to learning of SNNRF, so that the SNNRF became able to process on-line noise reduction. This paper showed theoretically that SNNRF behaves most optimally when the number of units in the hidden layer is equal to the rank of covariance matrix of signal component included in input signal. Computer experiments confirmed that SNNRF acquired appropriate characteristics for noise reduction from input signals, and remarkably improved the SN ratio of the signals.

In this paper, multi-head and finite-state transducers are proposed, and their computing abilities of number-theoretic functions are investigated. A multi-head transducer is an automaton which maps a unary input into a unary output using a finite number of input heads. A finite-state transduccer is one with single input head. First, it is shown that a two-way finite-state transducer is strictly more powerful than a one-way finite-state transducer, but a two-way finite-state transducer can be simulated by a two-scan finite-state transducer. As for the multi-head transducer, the following results are derived. The upper bound of increasing degree of functions computed by two-way multi-head transducers varies with the number of input heads. However, a two-way two-head transducer can compute an arbitrarily slowly increasing monotone total recursive function, so that there exists no lower bound of increasing degree of a function computed by it. Although the class of two-way multi-head transducers forms an infinite hierarchy of computing abilities with respect to the number of input heads, it is shown that a one-way multi-head transducer is equivalent to a two-way finite-state transducer provided that the number of input heads is more than one.

We present an Isometric Context-Free Array Grammar (ICFAG) that generates the set of all solid upright rectangles. This is performed by using the property that blank symbols in the rewriting rules enable ICFAGs to sense the local shapes of the host array. Thus ICFAGs are context-sensitive in some sense.