A Shared-State Hidden Markov Model (SS-HMM) has been widely used as an acoustic model in speech recognition. In this paper, we propose a method for constructing SS-HMMs within a practical Bayesian framework. Our method derives the Bayesian model selection criterion for the SS-HMM based on the variational Bayesian approach. The appropriate phonetic decision tree structure of the SS-HMM is found by using the Bayesian criterion. Unlike the conventional asymptotic criteria, this criterion is applicable even in the case of an insufficient amount of training data. The experimental results on isolated word recognition demonstrate that the proposed method does not require the tuning parameter that must be tuned according to the amount of training data, and is useful for selecting the appropriate SS-HMM structure for practical use.

Given a graph G, we give a fast algorithm for approximating the vertex connectivity κ of G. Our algorithm delivers a minimum vertex cut of G if κ δ/2, and returns a message "κ > δ/2" otherwise, where δ denotes the minimum degree of G. The algorithm runs in O(n²(1 + min {κ², κ/δ)) time and O(n + m) space, where n and m denote the numbers of vertices and edges in G, respectively.

We show that the necessary and sufficient condition for the existence of a balanced quatrefoil decomposition of the complete multigraph λK_n is n 9 and λ(n - 1) 0 (mod 24). Decomposition algorithms are also given.

A plane graph is a planar graph with a fixed embedding. In a no-bend orthogonal drawing of a plane graph, each vertex is drawn as a point and each edge is drawn as a single horizontal or vertical line segment. A planar graph is said to have a no-bend orthogonal drawing if at least one of its plane embeddings has a no-bend orthogonal drawing. In this paper we consider a class of planar graphs, called subdivisions of planar triconnected cubic graphs, and give a linear-time algorithm to examine whether such a planar graph G has a no-bend orthogonal drawing and to find one if G has.

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.

It is known that the original Grover Search (GS) can be modified to use a general value for the phase θ of the diffusion transform. Then, if the number of answers is relatively large, this modified GS can find one of the answers with probability one in a single iteration. However, such a quick and error-free GS can only be possible if we can initially adjust the value of θ correctly against the number of answers, and this seems very hard in usual occasions. A natural question now arises: Can we enjoy a merit even if GS is used without such an adjustment? In this paper, we give a positive answer using the balls-and-bins game in which the random sampling of bins is replaced by the quantum sampling, i.e., a single round of modified GS. It is shown that by using the quantum sampling: (i) The maximum load can be improved quadratically for the static model of the game and this improvement is optimal. (ii) That is also improved to O(1) for the continuous model if we have a certain knowledge about the total number of balls in the bins after the system becomes stable.

Cowen gave a universal compact routing algorithm with a stretch factor of three and table-size of O(n^2/3log^4/3n) based on a simple and practical model. (The table-size is later improved to O(n^1/2log^3/2n).) This paper considers, using the same model, how the necessary table-size differs if the stretch factor must be less than three. It is shown that: (i) There is a routing algorithm with a stretch factor of two whose table-size is (n -+ 2)log n. (ii) There is a network for which any routing algorithm that follows the model and with a stretch factor of less than three needs a table-size of (n - 2)log n in at least one node. Thus, we can only reduce roughly an additive log n (i.e., table-entries) from the trivial table-size of n log n which obviously enables shortest-path routing. Furthermore it turns out that we can reduce only an additive log n (i.e., only one table-entry) from the trivial n log n if we have to achieve a stretch factor of less than two. Thus the algorithm (i) is (roughly) tight both in its stretch factor and in its table-size.

Several grammars have been proposed for representing RNA secondary structure including pseudoknots such as simple linear tree adjoining grammar (sl-tag), extended sl-tag (esl-tag) and RNA pseudoknot grammar (rpg). The main purpose of this paper is to compare the generative power of these grammars by identifying them as subclasses of multiple context-free grammars (mcfg). Specifically, it is shown that the class of languages generated by esl-tag (ESL-TAL) properly includes the class of languages generated by sl-tag (SL-TAL) and the class of languages generated by cfg. Also, we show that the class of languages generated by rpg coincides with the class of languages generated by mcfg with dimension one or two and rank one or two. Furthermore, it is shown that SL-TAL is a full trio and ESL-TAL is a substitution closed full AFL.

This paper discusses real-time language recognition by 1-dimensional one-way cellular automata (OCAs) and two-way cellular automata (CAs), focusing on limitations of the parallel computation power. To clarify the limitations, we investigate real-time recognition of cyclic strings of the form u^k with u {0,1}⁺ and k 2. We show a version of pumping lemma for recognizing cyclic strings by OCAs, which can be used for proving that several languages are not recognizable by OCAs in real time. The paper also discusses the real-time language recognition of CAs by prefix and postfix computation, in which every prefix or postfix of an input string is also accepted, if the prefix or postfix is in the language. It is shown that there are languages L Σ⁺ such that L is not recognizable by OCA in real-time and the reversal of L and the concatenation LΣ^* are recognizable by CA in real-time.

Δ-Timed Atomic Broadcast is the broadcast ensuring that all correct processes deliver the same messages in the same order, and that delivery latency of any message broadcast by any correct process is some predetermined time Δ or less. In this paper, we propose a Δ-timed atomic broadcast algorithm in a synchronous system where communication delay is bounded by a known constant d and processes suffer both crash faults and timing faults. The proposed algorithm can tolerate f_c crash faults and f_t timing faults as long as at least f_t + 1 processes are correct, and its maximum delivery latency Δ is (2f' + 7)d where f' is the actual number of (crash or timing) faulty processes. That is, the algorithm attains the early-delivery in the sense that its delivery latency depends on the actual number of faults rather than the maximum number of faults that the algorithm can tolerate. Moreover, the algorithm has a distinct advantage of guaranteeing that timing-faulty processes also deliver the same messages in the same order as the correct processes (Uniformity). We also investigate the maximum number of faulty processes that can be tolerated. We show that no Δ-timed atomic broadcast algorithm can tolerate f_t timing faults, if at most f_t processes are correct. The impossibility result implies that the proposed algorithm achieves the maximum fault-resilience with respect to the number of faulty processes.

This paper presents an efficient scaling-simulation algorithm that simulates operations of the reconfigurable mesh (RM) of size n n using the mesh with multiple partitioned buses (MMPB) of size m m (m < n). The RM and the MMPB are the two-dimensional mesh-connected computers equipped with broadcasting buses. The broadcasting buses of the RM can be used to dynamically obtain various interconnection patterns among the processors during the execution of programs, while those of the MMPB are placed only to every row and column and are statically partitioned in advance by a fixed length. We show that the RM of size n n can be simulated in steps by the MMPB of size m m (m < n), where L is the number of broadcasting buses in each row/column of the simulating MMPB. Although the time-complexity of our algorithm is less efficient than that of the fastest RM scaling-simulation algorithm, the simulating model of our algorithm is the MMPB model where the bus-reconfiguration is not allowed.

This paper considers a neighborhood broadcasting protocol in undirected de Bruijn and Kautz networks. The neighborhood broadcasting problem(NBP) is the problem of disseminating a message from an originator vertex to only its neighbors. Our protocol works under the single-port and half-duplex model and solves NBP in 5log₂(n+1) + O(1) time units on the undirected de Bruijn graph UB(n,d) with n^d vertices and the undirected Kautz graph UK(n,d) with n^d + n^d-1 vertices, where 2n is the maximum degree of these graphs. This completion time is asymptotically optimal in this model.

For each positive integer r 1, a nondeterministic machine M is r path-bounded if for any input word x, there are r computation paths of M on x. This paper investigates the accepting powers of path-bounded one-way (simple) multihead nondeterministic finite automata. It is shown that for each k 2 and r 1, there is a language accepted by an (r + 1) path-bounded one-way nondeterministic k head finite automaton, but not accepted by any r path-bounded one-way nondeterministic k head finite automaton whether or not simple.

The number of satisfying assignments of k-CNF formulas is computed using the inclusion-exclusion formula for sets of clauses. Recently, it was shown that the information on the sets of clauses of size log k + 2 already uniquely determines the number of satisfying assignments of k-CNF formulas. The proof was, however, only existential and no explicit procedure was presented. In this paper, we show that such a procedure exists.

We show that a problem of deciding whether a formula for a multivariate polynomial of n variables over a finite field of characteristic 2 has degree n when reduced modulo a certain Boolean ideal belongs to P. When the formula is allowed to have succinct representations as sums of monomials, the problem becomes P-complete.

Adaptive routing algorithms, which dynamically select the route of a packet, have been widely studied for interconnection networks in massively parallel computers. An output selection function (OSF), which decides the output channel when some legal channels are free, is essential for an adaptive routing. In this paper, we propose a simple and efficient OSF called minimal multiplexed and least-recently-used (MMLRU). The MMLRU selection function has the following simple strategies for distributing the traffic: 1) each router locally grasps the congestion information by the utilization ratio of its own physical channels; 2) it is divided into the two selection steps, the choice from available physical channels and the choice from available virtual channels. The MMLRU selection function can be used on any type of network topology and adaptive routing algorithm. Simulation results show that the MMLRU selection function improves throughput and latency especially when the number of dimension becomes larger or the number of nodes per dimension become larger.

The traffic congestion problem in urban areas is worsening since traditional traffic signal control systems cannot provide] efficient traffic regulation. Therefore, dynamic traffic signal control in Intelligent Transportation System (ITS) recently has received increasing attention. This study devised a multi-agent architecture, the Adaptive and Cooperative Traffic light Agent Model (ACTAM), for a decentralized traffic signal control system. The proposed architecture comprises a data storage and communication layer, a traffic regulation factor processing layer, and a decision-making layer. This study focused on utilizing the cooperation of multi-agents and the prediction mechanism of our architecture, the Forecast Module, to forecast future traffic volume in each individual intersection. The Forecast Module is designed to forecast traffic volume in an intersection via multi-agent cooperation by exchanging traffic volume information for adjacent intersections, since vehicles passing through nearby intersections were believed to significantly influence the traffic volume of specific intersections. The proposed architecture can achieve dynamic traffic signal control. Thus, total delay time of the traffic network under ACTAM can be reduced by 37% compared to the conventional fixed sequence traffic signal control strategy. Consequently, traffic congestion in urban areas can be alleviated by adopting ACTAM.

One fundamental issue in multiagent reinforcement learning is how to deal with the limited local knowledge of an agent in order to achieve effective learning. In this paper, we argue that this issue can be more effectively solved if agents are equipped with a consistent global view. We achieve this by requiring agents to follow an interacting protocol. The properties of the protocol are derived and theoretically analyzed. A distributed protocol that satisfies these properties is presented. The experimental evaluations are conducted for a well-known test-case (i.e., pursuit game) in the context of two learning algorithms. The results show that the protocol is effective and the reinforcement learning algorithms using it perform much better.

We regard the events of a Markov decision process as the outputs from a Markov information source in order to analyze the randomness of an empirical sequence by the codeword length of the sequence. The randomness is an important viewpoint in reinforcement learning since the learning is to eliminate the randomness and to find an optimal policy. The occurrence of optimal empirical sequence also depends on the randomness. We then introduce the Lempel-Ziv coding for measuring the randomness which consists of the domain size and the stochastic complexity. In experimental results, we confirm that the learning and the occurrence of optimal empirical sequence depend on the randomness and show the fact that in early stages the randomness is mainly characterized by the domain size and as the number of time steps increases the randomness depends greatly on the complexity of Markov decision processes.

In this paper, we propose a wavelet-based fast motion estimation algorithm for video sequence encoding with a low bit-rate. By using one of the properties of wavelet transform, multi-resolution analysis (MRA), and the spatial interpolation of an image, we can simultaneously reduce the prediction error and the computational complexity inherent in video sequence encoding. In addition, by defining a significant block (SB) based on the differential information of wavelet coefficients between successive frames, the proposed algorithm enables us to make up for the increase in the number of motion vectors when the MRME algorithm is used. As a result, we are not only able to improve the peak signal-to-noise ratio (PSNR), but also reduce the computational complexity by up to 67%.

Analysis of speech acts and discourse structures is essential to a dialogue understanding system because speech acts and discourse structures are closely tied with the speaker's intention. However, it has been difficult to infer a speech act and a discourse structure from a surface utterance because they highly depend on the context of the utterance. We propose a statistical dialogue analysis model to determine discourse structures as well as speech acts using a maximum entropy model. The model can automatically acquire probabilistic discourse knowledge from an annotated dialogue corpus. Moreover, the model can analyze speech acts and discourse structures in one framework. In the experiment, the model showed better performance than other previous works.

Test compression / decompression is an efficient method for reducing the test application cost. In this letter we propose a response compression method based on Huffman coding. The proposed method guarantees zero-aliasing and it is independent of the fault model and the structure of a circuit-under-test. Experimental results of the compression ratio and the size of the encoder for the proposed method are presented.

We present a method for binarization of degraded call number images. Based on the texture feature of the character stroke, the algorithm initially detects the character pixels to determine the size of the local area and compute the logical thresholding level. Experimental results prove the effectiveness of the method.

The purpose of this study is to provide a new approach for detection using bio-impedance. This impedance is measured by the four-electrode method. As the impedance changes resulting from ankle, knee, and hip movements depended heavily on electrode placement, we determined the optimal electrode configurations for those movements by searching for high correlation coefficients, large impedance changes, and minimum interferences in ten subjects (Age: 204). Our optimal electrode configurations showed very strong relationships between the ankle joint angle and ankle impedance (γ = -0.9130.03), between the knee joint angle and knee impedance (γ = 0.9440.02), and between the hip joint angle and hip impedance (γ = 0.8230.08). This study showed the possibility that lower leg movement could be easily measured by impedance measurement system with two pairs of skin-electrodes.