In this paper, a recognition algorithm for the class of tree languages generated by linear, monadic context-free tree grammars (LM-CFTGs) is proposed. LM-CFTGs define an important class of tree languages because LM-CFTGs are weakly equivalent to tree adjoining grammars (TAGs). The algorithm uses the CKY algorithm as a subprogram and recognizes whether an input tree can be derived from a given LM-CFTG in O(n⁴) time, where n is the number of nodes of the input tree.

This paper considers the quantum query complexity of ε-biased oracles that return the correct value with probability only 1/2 + ε. In particular, we show a quantum algorithm to compute N-bit OR functions with O(/ε) queries to ε-biased oracles. This improves the known upper bound of O(/ε²) and matches the known lower bound; we answer the conjecture raised by the paper [1] affirmatively. We also show a quantum algorithm to cope with the situation in which we have no knowledge about the value of ε. This contrasts with the corresponding classical situation, where it is almost hopeless to construct a bounded error algorithm without knowing the value of ε.

For execution of computation-intensive applications, one of the most important paradigms is to divide the application into a large number of small independent tasks and execute them on heterogeneous parallel computing environments (abbreviated by HPCEs). In this paper, we aim to execute independent tasks efficiently on HPCEs. We consider the problem to find a schedule that maximizes the throughput of task execution for a huge number of independent tasks. First, for HPCEs where the network forms a directed acyclic graph, we show that we can find, in polynomial time, a schedule that attains the optimal throughput. Secondly, for arbitrary HPCEs, we propose an (+ε)-approximation algorithm for any constant ε(ε>0). In addition, we also show that the framework of our approximation algorithm can be applied to other collective communications such as the gather operation.

The aim of the paper is to design efficient bit-parallel algorithms for translating regular expressions into nondeterministic finite automata (NFAs). Let r be a regular expression over an alphabet Σ, and let n be the length of r and let m be the number of symbols of Σ occurring in r. Then we present bit-parallel algorithms for translating regular expressions into Glushkov automata (position automata) and follow automata using Thompson automata. For Glushkov automata, we will give an algorithm which runs in O(n+mm/W) time and space. For follow automata, we will give a randomized algorithm which runs in O(n+mm/W) expected time and O(n+mm/W) space. We rely on a W-bit uniform RAM for estimating the complexities of algorithms. Since the best known algorithms for these automata runs in O(n+m²) time and space, our algorithms achieve an almost W-fold speed-up.

We consider an edge-weighted graph G with a designated vertex v₀ such that weights of edges incident to v₀ may increase or decrease. We show that, with an O(mn+n²log n) time preprocessing, a minimum cut of the current G can be computed in O(log n) time per update of weight of any edge {v₀,u}.

We consider a problem for constructing a minimum cost r-edge-connected multigraph in which degree d(v) of each vertex v ∈ V is specified. In this paper, we propose a 3-approximation algorithm for this problem under the assumption that edge cost is metric, r(u,v) ∈ {1,2} for each u,v ∈ V, and d(v) ≥ 2 for each v ∈ V. This problem is a generalization of metric TSP. We also propose an approximation algorithm for the digraph version of the problem.

Let G be any graph with property P (for example, general graph, directed graph, etc.) and S be nonnegative and non-decreasing integer sequence(s). The prescribed degree sequence problem is a problem to determine whether there is a graph G having S as the prescribed sequence(s) of degrees or outdegrees of the vertices. From 1950's, P has attracted wide attentions, and its many extensions have been considered. Let P be the property satisfying the following (1) and (2):
(1) G is a directed graph with two disjoint vertex sets A and B.
(2) There are r₁₁ (r₂₂, respectively) directed edges between every pair of vertices in A(B), and r₁₂ directed edges between every pair of vertex in A and vertex in B.
Then G is called an (r₁₁, r₁₂, r₂₂)-tournament ("tournament", for short). The problem is called the score sequence pair problem of a "tournament" (realizable, for short). S is called a score sequence pair of a "tournament" if the answer of the problem is "yes." In this paper, we propose the characterizations of a score sequence pair of a "tournament" and an algorithm for determining in linear time whether a pair of two integer sequences is realizable or not.

Assume that each vertex of a graph G is assigned a constant number q of nonnegative integer weights, and that q pairs of nonnegative integers l_i and u_i, 1 ≤ i ≤ q, are given. One wishes to partition G into connected components by deleting edges from G so that the total i-th weights of all vertices in each component is at least l_i and at most u_i for each index i, 1 ≤ i ≤ q. The problem of finding such a "uniform" partition is NP-hard for series-parallel graphs, and is strongly NP-hard for general graphs even for q = 1. In this paper we show that the problem and many variants can be solved in pseudo-polynomial time for series-parallel graphs and partial k-trees, that is, graphs with bounded tree-width.

When Simulated Annealing (SA) is applied to continuous optimization problems, the design of the neighborhood used in SA becomes important. Many experiments are necessary to determine an appropriate neighborhood range in each problem, because the neighborhood range corresponds to distance in Euclidean space and is decided arbitrarily. We propose Multi-point Simulated Annealing with Adaptive Neighborhood (MSA/AN) for continuous optimization problems, which determine the appropriate neighborhood range automatically. The proposed method provides a neighborhood range from the distance and the design variables of two search points, and generates candidate solutions using a probability distribution based on this distance in the neighborhood, and selects the next solutions from them based on the energy. In addition, a new acceptance judgment is proposed for multi-point SA based on the Metropolis criterion. The proposed method shows good performance in solving typical test problems.

In this paper we study the problem of how to identify multiple disjoint paths that have the minimum total cost OPT and satisfy a delay bound D in a graph G. This problem has lots of applications in networking such as fault-tolerant quality of service (QoS) routing and network-flow load balancing. Recently, several approximation algorithms have been developed for this problem. Here, we propose a new approximation algorithm for it by using the Lagrangian Relaxation method. We then present a simple approximation algorithm for finding multiple link-disjoint paths that satisfy the delay constraints at a reasonable total cost. If the optimal solution under delay-bound D has a cost OPT, then our algorithm can find a solution whose delay is bounded by (1+)D and the cost is no more than (1+k)OPT. The time complexity of our algorithm is much better than the previous algorithms.

A novel configuration method called Row Multicast Configuration (RoMultiC) is proposed for high speed configuration of coarse grain reconfigurable systems. The same configuration data can be transferred in multicast fashion to configure many Processing Elements (PEs) by using a multicast bit-map provided in row and column directions of PE array. Evaluation results using practical applications show that a model reconfigurable system that incorporates this scheme can reduce configuration clock cycles by up to 73.1% compared with traditional configuration delivery scheme. Amount of required memory to store the configuration data at external memory is also reduced by omitting the duplicated configuration data.

This paper proposes a Dynamic-Configurable NAT (DCNAT) approach to the inbound session problem for private networks behind NAT routers. DCNAT is a port-based NAT scheme that adopts a registration procedure for a host to register a session with a DCNAT router before originating a communication session to a host behind the DCNAT router. With the registration procedure, the DCNAT router can create NAT binding entries dynamically for address: port translation before the inbound session starts. Furthermore the dynamic creation of NAT binding entries makes DCNAT very flexible in supporting inbound accesses to a large number of services opened dynamically by the private nodes behind an NAT router. Although DCNAT requires minor modification to the originating host and the NAT router, it is highly suitable for proxy-based applications, such as web browsing, or instant message delivery.

We propose a model for constructing a multilayered boundary in an information system to defend against intrusive anomalies by correlating a number of parametric anomaly detectors. The model formulation is based on two observations. First, anomaly detectors differ in their detection coverage or blind spots. Second, operating environments of the anomaly detectors reveal different information about system anomalies. The correlation among observation-specific anomaly detectors is first formulated as a Partially Observable Markov Decision Process, and then a policy-gradient reinforcement learning algorithm is developed for an optimal cooperation search, with the practical objectives being broader overall detection coverage and fewer false alerts. A host-based experimental scenario is developed to illustrate the principle of the model and to demonstrate its performance.

Fitts' law has been applied in many studies to evaluate pointing tasks. However, the quantitative effect of using color in the interfaces has not been discussed in the literature. This paper introduces research on the effects of color in pointing tasks using Fitts' law as the evaluation method. Different colors and color presentation styles are applied in the experiments which are similar in design to the paradigmatic Fitts' law pointing task. The experimental results show that when the subjects use a mouse as the input device, there is no significant difference between an interface with a colored target and one with a white target in the mean performance time. The results also reveal that color presentation styles will offer no significant difference to pointing tasks when the mouse is applied. However, when the interface of tablet PC and pen was applied, subjects without much experience in tablet personal computer usage needed more time to perform the task with colored targets than with a white target. Furthermore, when the colors are changed randomly during the selection process, the difference is even more obvious. These results are confirmed by a Checking Experiment and a Learning Effect Experiment which we performed on different groups of subjects.

Thanks to recent improvements in road heating technology, traffic problems due to icy roads are decreasing. However, there has always been concern about the high operational and maintenance cost associated with road heating. One way to reduce the cost is to reduce the time when power is applied for preheating because it is often applied even when a road is not likely to be icy. The authors believe that, if it is possible to forecast accurately whether a road will become icy, unnecessary preheating can be greatly reduced. This paper presents an algorithm for forecasting physical road conditions. The algorithm divides the weather conditions that people perceive daily into 11 patterns. The comparison between the changes in road conditions as determined by our method and known changes in road conditions has shown a 12% increase over previous methods in forecasting accuracy.

In this paper, we address the problem of the rotation-invariant texture analysis. For this purpose, we first present a modified version of the discrete Radon transform whose performance, including accuracy and processing time, is significantly better than the conventional transform in direction estimation and categorization of textural images. We then utilize this transform with a rotated version of Gabor filters to propose a new scheme for texture classification. Experimental results on a set of images from the Brodatz album indicate that the proposed scheme outperforms previous works.

In this paper, we address the task of incremental language modeling for automatic transcription of broadcast news speech. Daily broadcast news naturally contains new words that are not in the lexicon of the speech recognition system but are important for downstream applications such as information retrieval or machine translation. To recognize those new words, the lexicon and the language model of the speech recognition system need to be updated periodically. We propose a method of estimating a list of words to be added to the lexicon based on some time-series text data. The experimental results on the RT04 Broadcast News data and other TV audio data showed that this method provided an impressive and stable reduction in both out-of-vocabulary rates and speech recognition word error rates.

In speaker adaptation for speech synthesis, it is desirable to convert both voice characteristics and prosodic features such as F0 and phone duration. For simultaneous adaptation of spectrum, F0 and phone duration within the HMM framework, we need to transform not only the state output distributions corresponding to spectrum and F0 but also the duration distributions corresponding to phone duration. However, it is not straightforward to adapt the state duration because the original HMM does not have explicit duration distributions. Therefore, we utilize the framework of the hidden semi-Markov model (HSMM), which is an HMM having explicit state duration distributions, and we apply an HSMM-based model adaptation algorithm to simultaneously transform both the state output and state duration distributions. Furthermore, we propose an HSMM-based adaptive training algorithm to simultaneously normalize the state output and state duration distributions of the average voice model. We incorporate these techniques into our HSMM-based speech synthesis system, and show their effectiveness from the results of subjective and objective evaluation tests.

We have previously developed a concatenative speech synthesizer based on the plural speech unit selection and fusion method that can synthesize stable and human-like speech. In this method, plural speech units for each speech segment are selected using a cost function and fused by averaging pitch-cycle waveforms. This method has a large computational cost, but some platforms require a speech synthesis system that can work within limited hardware resources. In this paper, we propose an offline unit fusion method that reduces the computational cost. In the proposed method, speech units are fused in advance to make a pre-fused speech unit database. At synthesis time, a speech unit for each segment is selected from the pre-fused speech unit database and the speech waveform is synthesized by applying prosodic modification and concatenation without the computationally expensive unit fusion process. We compared several algorithms for constructing the pre-fused speech unit database. From the subjective and objective evaluations, the effectiveness of the proposed method is confirmed by the results that the quality of synthetic speech of the offline unit fusion method with 100 MB database is close to that of the online unit fusion method with 93 MB JP database and is slightly lower to that of the 390 MB US database, while the computational time is reduced by 80%. We also show that the frequency-weighted VQ-based method is effective for construction of the pre-fused speech unit database.

In real-time speech recognition applications, there is a need to implement a fast and reliable adaptation algorithm. We propose a method to reduce adaptation time of the rapid unsupervised speaker adaptation based on HMM-Sufficient Statistics. We use only a single arbitrary utterance without transcriptions in selecting the N-best speakers' Sufficient Statistics created offline to provide data for adaptation to a target speaker. Further reduction of N-best implies a reduction in adaptation time. However, it degrades recognition performance due to insufficiency of data needed to robustly adapt the model. Linear interpolation of the global HMM-Sufficient Statistics offsets this negative effect and achieves a 50% reduction in adaptation time without compromising the recognition performance. Furthermore, we compared our method with Vocal Tract Length Normalization (VTLN), Maximum A Posteriori (MAP) and Maximum Likelihood Linear Regression (MLLR). Moreover, we tested in office, car, crowd and booth noise environments in 10 dB, 15 dB, 20 dB and 25 dB SNRs.

In this paper, we present an efficient architecture for connected word recognition that can be implemented with field programmable gate array (FPGA). The architecture consists of newly derived two-level dynamic programming (TLDP) that use only bit addition and shift operations. The advantages of this architecture are the spatial efficiency to accommodate more words with limited space and the absence of multiplications to increase computational speed by reducing propagation delays. The architecture is highly regular, consisting of identical and simple processing elements with only nearest-neighbor communication, and external communication occurs with the end processing elements. In order to verify the proposed architecture, we have also designed and implemented it, prototyping with Xilinx FPGAs running at 33 MHz.

We present here a simple technique for parametrization of popular biorthogonal wavelet filter banks (BWFBs) having vanishing moments (VMs) of arbitrary multiplicity. Given a prime wavelet filter with VMs of arbitrary multiplicity, after formulating it as a trigonometric polynomial depending on two free parameters, we prove the existence of its dual filter based on the theory of Diophantine equation. The dual filter permits perfect reconstruction (PR) and also has VMs of arbitrary multiplicity. We then give the complete construction of two-parameter families of 17/11 and 10/18 BWFBs, from which any linear-phase 17/11 and 10/18 BWFB possessing desired features could be derived with ease by adjusting the free parameters. In particular, two previously unpublished BWFBs for embedded image coding are constructed, both have optimum coding gains and rational coef ficients. Extensive experiments show that our new BWFBs exhibit performance equal to Winger's W-17/11 and Villasenor's V-10/18 (superior to CDF-9/7 by Cohen et al. and Villasenor's V-6/10) for image compression, and yet require slightly lower computational costs.

We compare the convergence performance of different numerical schemes for computing the fundamental matrix from point correspondences over two images. First, we state the problem and the associated KCR lower bound. Then, we describe the algorithms of three well-known methods: FNS, HEIV, and renormalization. We also introduce Gauss-Newton iterations as a new method for fundamental matrix computation. For initial values, we test random choice, least squares, and Taubin's method. Experiments using simulated and real images reveal different characteristics of each method. Overall, FNS exhibits the best convergence properties.

Diseases of the gastro-intestinal tract are becoming more prevalent. New techniques and devices, such as the wireless capsule endoscope and the telemetry capsule, that are able to measure the various signals of the digestive organs (temperature, pH, and pressure), have been developed for the observation of the digestive organs. In these capsule devices, there are no methods of moving and grasping them. In order to make a swift diagnosis and to give proper medication, it is necessary to control the moving speed of the capsule. This paper presents a wireless system for the control of movements of an electrical stimulus capsule. This includes an electrical stimulus capsule which can be swallowed and an external transmitting control system. A receiver, a receiving antenna (small multi-loop), a transmitter, and a transmitting antenna (monopole) were designed and fabricated taking into consideration the MPE, power consumption, system size, signal-to-noise ratio and the modulation method. The wireless system, which was designed and implemented for the control of movements of the electrical stimulus capsule, was verified by in-vitro experiments which were performed on the small intestines of a pig. As a result, we found that when the small intestines are contracted by electrical stimuli, the capsule can move to the opposite direction, which means that the capsule can go up or down in the small intestines.

One of the system greatly affecting the performance of a database server is the size-division of buffer pools. This letter proposes an adaptive control method of the buffer pool sizes. This method obtains the nearly optimal division using only observed response times in a comparatively short duration.

In this paper, we propose TB-MAC (Threshold-Based MAC), which has been designed to consider various network traffic conditions while providing energy efficiency in a wireless sensor networks. Existing MAC protocols for sensor networks attempt to solve the energy consumption problem caused by idle listening using an active/sleep duty cycle. Since there are various traffic conditions, however, they may not always provide improvements in energy consumption. Hence, we propose a MAC protocol algorithm that stores data in a buffer and transmits data when the buffer exceeds a threshold value so that energy efficiency is always guaranteed for any network traffic condition. The analytical results show that our proposed algorithm enables significant improvements in energy consumption compared to the existing MAC protocols for sensor networks.

In this letter, we propose a new approach to estimate the degree of noise masking based on a sophisticated model for clean speech distribution. This measure, named as noise masking probability (NMP), is incorporated into the feature compensation technique to achieve robust speech recognition in noisy environments. Experimental results show that the proposed approach improves the performance of the baseline recognition system in the presence of various background noises.

A direction-oriented spatial interpolation technique for image de-interlacing is presented in this letter. The experimental results demonstrate that our method achieves excellent performance in terms of both objective and subjective image quality. The proposed algorithm also has a very computationally simple structure, and proves to be a good candidate for low-cost hardware interpolator.

Context-based adaptive binary arithmetic coding (CABAC) is the major entropy-coding algorithm employed in H.264/AVC. Although the performance gain of H.264/AVC is mainly due to CABAC, it is difficult to achieve a fast decoder because the decoding algorithm is basically sequential and computationally intensive. In this letter, a prediction scheme is proposed that enhances overall decoding performance by decoding two binary symbols at a time. A CABAC decoder based on the proposed prediction scheme improves the decoding performance by 24% compared to conventional decoders.