This paper investigates the accepting powers of multi-inkdot two-way alternating pushdown automata (Turing machines) with sublogarithmic space and constant leaf-size. For each k1, and each m0, let weak-ASPACEm [L(n),k] denote the class of languages accepted by simultaneously weakly L(n) space-bounded and k leaf-bounded m-inkdot two-way alternating Turing machines, and let strong-2APDAm[L(n),k] denote the class of languages accepted by simultaneously strongly L(n) space-bounded and k leaf-bounded m-inkdot two-way alternating pushdown automata. We show that(1) strong-2APDAm [log log n,k+1]weak-ASPACEm[o(log n),k]φfor each k1 and each m1, and(2) strong-2APDA(m+1) [log log n,k]weak-ASPACEm[o(log n),k]φfor each k1 and each m0.

In [2] Ibarra introduced a restricted version of one-way multihead pushdown automaton (PDA), called a simple one-way multihead PDA, and showed that such machines recognize only languages with semilinear property. The main result of this paper is that for each k 1, simple (sensing) one-way (k + 1)-head PDA's are more powerful than simple (sensing) one-way k-head PDA's. This paper also investigates closure properties for simple (sensing) one-way multihead PDA's

We analytically evaluated the effects of the analog components on a high-speed downlink packet access (HSDPA) system standardized by 3GPP. We considered the phase noise of synthesizers, the imbalance of demodulators between in-phase and quadrature channels, and the filters. The components are represented by the appropriate equations. We applied adaptive modulation and coding methods for HSDPA systems and base station transmission of adequate data rate signals complying with quality estimated by mobile stations (MSs). The quality represents a data rate indicating that MSs can receive the signals. We estimated the quality using a conventional signal-to-interference measurement of the common pilot channel (CPICH) and found that the phase noise creates a mismatch relationship between the quality and the data rate, while the demodulator imbalance and filters create a suitable relationship. We confirmed this using analytic methods and computer simulation.

This paper investigates closure properties of one-pebble Turing machines with sublogarithmic space. It shows that for any function log log n L(n) = o(log n), neither of the classes of languages accepted by L(n) space-bounded deterministic and self-verifying nondeterministic one-pebble Turing machines is closed under concatenation, Kleene closure, and length-preserving homomorphism.

Recently, we introduced a new automata model, so-called colored finite automata (CFAs) whose accepting states are multi-colored (i.e., not conventional black-and-white acceptance) in order to classify their input strings into two or more languages, and solved the specific complexity problems concerning color-unmixedness of nondeterministic CFA. That is, so-called UV, UP, and UE problems are shown to be NLOG-complete, P, and NP-complete, respectively. In this paper, we apply the concept of colored accepting mechanism to pushdown automata and show that the corresponding versions of the above-mentioned complexity problems are all undecidable. We also investigate the case of unambiguous pushdown automata and show that one of the problems turns out to be permanent true (the others remain undecidable).

We studied transient fields on a perfectly conducting sphere excited by a half sine pulse wave and examined the Poynting vectors, the energy densities and the energy velocities of the creeping waves. We used FILT (Fast Inversion of Laplace Transform) method for transient analysis. We compared the amplitudes of the creeping wave with that of steady state high frequency approximation obtained by the Watson transformation. The main results are: (1) We confirmed in the transient response that the pulse propagates clockwise and counterclockwise along the geodesic circumference. (2) In the transient electromagnetic field observed in the E-plane we can recognize creeping waves clearly. (3) The existence of creeping waves is not clear in the H-plane. (4) The pulse wave propagation on the sphere is seen more clearly from the Poynting vectors and the energy densities than the field components. (5) The energy velocity of the wave front is equal to the light velocity as should be. The energy velocity of the wave body becomes smaller with the passage of time. (6) The amplitude of the creeping wave for a beat pulse and the amplitude obtained by the Watson transform for mono spectrum agree in the order of relative error below 25%.

We report the dispersion of two-photon absorption (TPA) coefficient, (β), in polydiacetylene (12, 8) thin film waveguides in the wavelength range less than the one-photon band-gap with a 100 femtosecond mode-locked Ti: Sapphire laser pulses. The TPA coefficient was found to be 4 cm/GW for TE polarization at 900 nm (1.38 eV) by taking into account a Gaussian intensity distribution as well as a temporal pulse shape. We observed a sharp resonance in β above the first one-photon allowed transition with a full width at half maximum (FWHM) of 90 meV.

This paper establishes a relationship among the accepting powers of deterministic, nondeterministic, and alternating one-way auxiliary pushdown automata, for any tape bound below n. Some other related results are also presented.

One-way sensing simple multihead finite automata with bounds on the number of times of use of sensing function in accepting computations are studied. It is shown that the languages accepted by one-way sensing simple multihead finite automata with constant sensing function bound satisfy the semilinear property, and that for one-way sensing simple multihead finite automata, m+1 times of the use of sensing function are better than m.

We are aming to develop a computer-based consultant system which helps novice computer users to achieve their task goals on computers through natural language dialogues. Our target is spoken Japanese. To develop effective methods for processing spoken Japanese, it is essential to analyze real dialogues and to find the characteristics of spoken Japanese. In this paper, we discuss the design problems associated with constructing a spoken dialogue database from the viewpoint of advisory dialogue collection, describe XMH (X-window-based electronic mail handling program) usage experiments made to collect advisory dialogues between novice XMH users and an expert consultant, and show the dialogue database we constructed from these dialogues. The main features of our database are as follows: (1) Our target dialogues were advisory ones. (2) The advisory dialogues were all related to the use of XMH that has a visual interface operated by a keyboard and a mouse. (3) The primary objective of the users was not to engage in dialogues but to achieve specific task goals using XMH. (4) Not only what the users said but also XMH operations performed by the users are included as dialogue elements. This kind of dialogue database is a very effective source for developing new methods for processing spoken language in multimodal consultant systems, and we have therefore made it available to the public. Based on our analysis of the database, we have already developed several effective methods such as a method for recognizing user's communicative intention from a transcript of spoken Japanese, and a method for controlling dialogues between a novice XMH user and the computer-based consultant system which we are developing. Also, we have proposed several response generation rules as the response strategy for the consultant system. We have developed an experimental consultant system by implementing the above methods and strategy.

Let SeH{0}(k) [NSeH{0}(k)] denote the class of languages over a one-letter alphabet accepted by two-way sensing deterministic [nondeterministic] k-head finite automata. This paper shows that (i) SeH{0}(2)SeH{0}(3), and (ii) NSeH{0}(2) NSeH{0}(3). This gives an affirmative answer to an open problem in Ref. [3].

This paper investigates a relationship between accepting powers of two-way deterministic one-counter automata and one-pebble off-line deterministic Turing machines operating in space between loglog n and log n, and shows that they are incomparable.

In our previous paper, we had proved that the non-closure properties of the class of sets accepted by three-way two-dimensional alternating finite automata (L[TR2-AFA]) under several operations, i.e., row catenation, row closure, row cyclic closure, and projection operations. This letter investigates the remaining closure properties of L[TR2-AFA], especially under column-directional operations, showing that this class L[TR2-AFA] is not closed under column catenation, column closure, or column cyclic closure operations, too. Thus, we have settled the almost closure properties of L[TR2-AFA].

Given a binary picture represented by a region quadtree, it is desirable to identify the amount of (rightward and downward) shifts of the foreground components such that it gives the minimum number of nodes of its quadtree. This problem is called "quadtree normalization. " For this problem, it is unknown whether there exists a linear time algorithm with respect to the size of given images (i. e. , the number of pixels). In this study, we investigate the "one-dimensional version" of the quadtree normalization problem, i. e. , given a binary string represented by a regional binary tree, the task is to identify the amount of (rightward) shift of the foreground components such that it gives the minimum number of nodes of its binary tree. We show that there exists a linear time algorithm for this version.

This paper introduces a probabilistic rebound automaton (pra), and investigates its accepting power and closure property. We show that (1) the class of languages recognized by pra's with error probability less than 1/2, PRA, is incomparable with the class of context-free languages, (2) there is a language accepted by a two-way nondeterministic one counter automaton, but not in PRA, and (3) there is a language accepted by a deterministic one-marker rebound automaton, but not in PRA. We also show that PRA is not closed under concatenation and Kleene + .

This paper first investigates a relationship between inkdot-depth and inkdot-size of inkdot two-way alternating Turing machines and pushdown automata with sublogarithmic space, and shows that there exists a language accepted by a strongly loglog n space-bounded alternating pushdown automaton with inkdot-depth 1, but not accepted by any weakly o (log n) space-bounded and d (n) inkdot-size bounded alternating Turing machine, for any function d (n) such that limn [d (n)log n/n1/2] = 0. In this paper, we also show that there exists an infinite space hierarchy among two-way alternating pushdown automata with sublogarithmic space.

This paper investigates some fundamental properties of alternating one-way (or two-way) pushdown automata (pda's) with sublogarithmic space. We first show that strongly (weakly) sublogarithmic space-bounded two-way alternating pda's are more powerful than one-way alternating pda's with the same space-bound. Then, we show that weakly sublogarithmic space-bounded two-way (one-way) alternating pda's are more powerful than two-way (one-way) nondeterministic pda's and alternating pda's with only universal states using the same space, and we also show that weakly sublogarithmic space-bounded one-way nondeterministic Turing machines are incomparable with one-way alternating Turing machines with only universal states using the same space. Furthermore, we investigate several fundamental closure properties, and show that the class of languages accepted by weakly sublogarithmic space-bounded one-way alternating pda's and the class of languages accepted by sublogarithmic space-bounded two-way deterministic pda's (nondeterministic pda's, alternating pda's with only universal states) are not closed under concatenation, Kleene closure, and length preserving homomorphism. Finally, we briefly investigate a relationship between 'strongly' and 'weakly'.

Inoue et al. introduced an automaton on a two-dimensional tape, which decides acceptance or rejection of an input tape by scanning the tape from various sides by various automata which move one way, and investigated the accepting power of such an automaton. This paper continues the investigation of this type of automata, especially, -type automata (obtained by combining four three-way two-dimensional deterministic finite automata (tr2-dfa's) in "or" fashion) and -type automata (obtained by combining four tr2-dfa's in "and" fashion). We first investigate a relationship between the accepting powers of -type automata and -type automata, and show that they are incomparable. Then, we investigate a hierarchy of the accepting powers based on the number of tr2-dfa's combined. Finally, we briefly describe a relationship between the accepting powers of automata obtained by combining three-way two-dimensional deterministic and nondeterministic finite automata.

This paper is concerned with a comparative study of the accepting powers of deterministic, Las Vegas, self-verifying nondeterminisic, and nondeterministic (simple) multihead finite automata. We show that (1) for each k 2, one-way deterministic k-head (resp., simple k-head) finite automata are less powerful than one-way Las Vegas k-head (resp., simple k-head) finite automata, (2) there is a language accepted by a one-way self-verifying nondeterministic simple 2-head finite automaton, but not accepted by any one-way deterministic simple multihead finite automaton, (3) there is a language accepted by a one-way nondeterministic 2-head (resp., simple 2-head) finite automaton, but not accepted by any one-way self-verifying nondeterministic multihead (resp., simple multihead) finite automaton, (4) for each k 1, two-way Las Vegas k-head (resp., simple k-head) finite automata have the same accepting powers as two-way self-verifying nondeterministic k-head (resp., simple k-head) finite automata, and (5) two-way Las Vegas simple 2-head finite automata are more powerful than two-way deterministic simple 2-head finite automata.

Some textbooks of formal languages and automata theory implicitly state the structural equality of the binary n-dimensional de Bruijn graph and the state diagram of minimum state deterministic finite automaton which accepts regular language (0+1)*1(0+1)n-1. By introducing special finite automata whose accepting states are refined with two or more colors, we extend this fact to both k-ary versions. That is, we prove that k-ary n-dimensional de Brujin graph and the state diagram for minimum state deterministic colored finite automaton which accepts the (k-1)-tuple of the regular languages (0+1+…+k-1)*1(0+1+…+k-1)n-1,...,and(0+1+…+k-1)*(k-1)(0+1+…+k-1)n-1 are isomorphic for arbitrary k more than or equal to 2. We also investigate the properties of colored finite automata themselves and give computational complexity results on three decision problems concerning color unmixedness of nondeterminisitic ones.