A new edge-coloring algorithm for bipartite graphs is presented. This algorithm, based on the framework of the O(m log d + (m/d) log (m/d) log d) algorithm by Makino-Takabatake-Fujishige and the O(m log m) one by Alon, finds an optimal edge-coloring of a bipartite graph with m edges and maximum degree d in O(m log d + (m/d) log (m/d)) time. This algorithm does not require elaborate data structures, which the best known O(m log d) algorithm due to Cole-Ost-Schirra depends on.

Recently, Das et al. proposed a dynamic ID-based verifier-free password authentication scheme using smart cards. To resist the ID-theft attack, the user's login ID is dynamically generated and one-time used. Herein, we demonstrate that Das et al.'s scheme is vulnerable to an impersonation attack, in which the adversary can easily impersonate any user to login the server at any time. Furthermore, we also show several minor weaknesses of Das et al.'s scheme.

In this study, a cascade open-short-thru (COST) de-embedding procedure is proposed for the first time for on-wafer device characterization in the RF/microwave frequency regime. This technique utilizes the "open" and "short" dummy structures to de-embed the probe-pad parasitics of a device-under-test (DUT). Furthermore, to accurately estimate the input/output interconnect parasitics, including the resistive, inductive, capacitive, and conductive components, the "thru" dummy device has been characterized after probe-pad de-embedding. With the combination of transmission-line theory and cascade-configuration concept, this method can efficiently generate the scalable and repeatable interconnect parameters to completely eliminate the redundant parasitics of the active/passive DUTs of various device sizes and interconnect dimensions. Consequently, this method is very suitable for the on-wafer automatic measurement.

Web browsing task is based on depth-first searching scheme, so that searching relevant information from Web may be very tedious. In this paper, we propose personal browsing assistant system based on user intentions modeling. Before explicitly requested by a user, this system can analyze the prefetched resources from the hyperlinked Webpages and compare them with the estimated user intention, so that it can help him to make a better decision like which Webpage should be requested next. More important problem is the semantic heterogeneity between Web spaces. It makes the understandability of locally annotated resources more difficult. We apply semantic annotation, which is a transcoding procedure with the global ontology. Therefore, each local metadata can be semantically enriched, and efficiently comparable. As testing bed of our experiment, we organized three different online clothes stores whose images are annotated by semantically heterogeneous metadata. We simulated virtual customers navigating these cyberspaces. According to the predefined preferences of customer models, they conducted comparison-shopping. We have shown the reasonability of supporting the Web browsing, and its performance was evaluated as measuring the total size of browsed hyperspace.

Fundamentals of parametric processing in highly nonlinear optical fiber are reviewed. Experimental procedures necessary for construction of one- and two-pump parametric amplifier architectures are described. Pump phase broadening, dispersion fluctuation and birefringence form basic impairment mechanisms in fiber parametric devices and are analyzed in two-pump parametric devices. Parametric signal processing is introduced with specific applications in all-optical regeneration, band conjugation, multicasting, packet switching and signal distortion reversal.

Let G = (V,E) be a connected graph such that each edge e ∈ E and each vertex v ∈ V are weighted by nonnegative reals w(e) and h(v), respectively. Let r be a vertex designated as a root, and p be a positive integer. The minmax rooted-subtree cover problem (MRSC) asks to find a partition X = {X1,X2,...,Xp of V and a set of p subtrees T1,T2,...,Tp such that each Ti contains Xi∪{r} so as to minimize the maximum cost of the subtrees, where the cost of Ti is defined to be the sum of the weights of edges in Ti and the weights of vertices in Xi. Similarly, the minmax rooted-cycle cover problem (MRCC) asks to find a partition X = {X1,X2,...,Xp} of V and a set of p cycles C1,C2,...,Cp such that Ci contains Xi∪{r} so as to minimize the maximum cost of the cycles, where the cost of Ci is defined analogously with the MRSC. In this paper, we first propose a (3-2/(p+1))-approximation algorithm to the MRSC with a general graph G, and we then give a (6-4/(p+1))-approximation algorithm to the MRCC with a metric (G,w).

We present a simple decoding algorithm that modifies soft bit-flipping algorithm for decoding LDPC codes. In our method, a new parameter is explored to distinguish the variables (symbols) belonging to the same number of unsatisfied constraints. A token is also assigned in the method to avoid repeated flipping of the same variable, rather than using a constant taboo length. Our scheme shows a similar computational load as the taboo-based algorithm, while having a similar decoding performance as the belief propagation algorithm.

We propose a method of controlling the view divergence of data freshness when copies of sites in a replicated database are updated asynchronously. The view divergence of the replicated data freshness is the difference in the recentness of the updates reflected in the data acquired by clients. Our method accesses multiple sites and provides a client with data that reflects all the updates received by the sites. First, we define the probabilistic recentness of updates reflected in acquired data as read data freshness (RDF). The degree of RDF of data acquired by clients is the range of view divergence. Second, we propose a way to select sites in a replicated database by using the probability distribution of the update delays so that the data acquired by a client satisfies its required RDF. This way calculates the minimum number of sites in order to reduce the overhead of read transactions. Our method continues to adaptively and reliably provide data that meets the client's requirements in an environment where the delay of update propagation varies and applications' requirements change depending on the situation. Finally, we evaluate by simulation the view divergence we can control using our method. The simulation showed that our method can control the view divergence to about 1/4 that of a normal read transaction for 100 replicas. In addition, the increase in the overhead of a read transaction imposed by our method is not as much as the increase in the total number of replicas.

We propose source coding algorithms that use the randomness of a past sequence. The proposed algorithms solve the problems of multi-terminal source coding, rate-distortion source coding, and source coding with partial side information at the decoder. We analyze the encoding rate and the decoding error rate in terms of almost-sure convergence.

This paper presents a novel approach to improving the IDDQ-based diagnosability of a CMOS circuit by dividing the circuit into independent partitions and using a separate power supply for each partition. This technique makes it possible to implement multiple IDDQ measurement points, resulting in improved IDDQ-based diagnosability. The paper formalizes the problem of partitioning a circuit for this purpose and proposes optimal and heuristic based solutions. The effectiveness of the proposed approach is demonstrated through experimental results.

A b-bit SIMD functional unit has n k-bit sub-functional units in itself, where b = k n. It can execute n-parallel k-bit operations. However, all the b-bit functional units in a processor core do not necessarily execute n-parallel operations. Depending on an application program, some of them just execute n/2-parallel operations or even n/4-parallel operations. This means that we can modify a b-bit SIMD functional unit so that it has n/2 k-bit sub-functional units or n/4 k-bit sub-functional units. The number of k-bit sub-functional units in a SIMD functional unit is called sub-operation parallelism. We incorporate a sub-operation parallelism optimization algorithm into SIMD functional unit optimization. Our proposed algorithm gradually reduces sub-operation parallelism of a SIMD functional unit while the timing constraint of execution time satisfied. Thereby, we can finally find a processor core with small area under the given timing constraint. We expect that we can obtain processor core configurations of smaller area in the same timing constraint rather than a conventional system. The promising experimental results are also shown.

Programmable Logic Controller (PLC) has been widely used in the industrial control. Inherently, the PLC-based system is a class of Hybrid Dynamical System (HDS) in which continuous state of the plant is controlled by the discrete logic-based controller. This paper firstly presents the formal algebraic model of the PLC-based control systems which enable the designer to formulate the various kinds of optimization problem. Secondly, the optimization problem of the 'sensor parameters,' such as the location of the limit switch in the material handling system, the threshold temperature of the thermostat in the temperature control system, is addressed. Finally, we formulate this problem as Mixed Logical Dynamical Systems (MLDS) form which enables us to optimize the sensor parameters by applying the Mixed Integer Programming.

We propose a low-power resource-shared VLIW processor (RSVP) for future leaky nanometer process technologies. It consists of several single-way independent processor units (IPUs) that share parallel processor resources. Each IPU works as a variable-way VLIW processor sharing the parallel resources according to priorities of given tasks. RSVP allocates shared parallel resources to the IPUs cycle by cycle. It can minimize the number of NOPs that is wasting power. The performance per power (P3) of a 4-parallel 4-way RSVP that corresponds to four 4way VLIWs is 3.7% better than a conventional 4-parallel 4-way VLIW multiprocessor in the current 90 nm process. We estimate that the RSVP achieves 36% less leakage power and 28% better P3 in the future 25 nm process. We have fabricated an RSVP test chip that contains two IPU and a shared resource equivalent to two 2way VLIWs in a 180 nm process. It is functional at 100 MHz clock speed and its power is 130 mW.

This paper proposes an iterative parallel genetic algorithm with biased initial population to solve large-scale combinatorial optimization problems. The proposed scheme employs a master-slave collaboration in which the master node manages searched space of slave nodes and assigns seeds to generate initial population to slaves for their restarting of evolution process. Our approach allows us as widely as possible to search by all the slave nodes in the beginning period of the searching and then focused searching by multiple slaves on a certain spaces that seems to include good quality solutions. Computer experiment shows the effectiveness of our proposed scheme.

In this paper, low-power design techniques of high-speed A/D converters are reviewed and discussed. Pipeline and parallel-pipeline architectures are treated as these are dominant architectures when required high sampling rate and high resolution with reasonable power dissipation. A systematic approach to the power optimization of pipeline and parallel pipeline ADC's is introduced based on models of noise analysis and response time of a building block in the multiple-stage pipeline ADC. Finally, the theoretical minimum of required power as functions of the sampling rate, resolution and SNR is discussed. The analysis shows that, with the developments of new circuits and systems to approach to the minimum, the power can be further reduced by a factor of more than 1/10 without changing the basic architectures.

This paper considers the problem of recursive filtering for linear discrete-time systems with uncertain observation. A new approximate adaptive filter with a parallel structure is herein proposed. It is based on the optimal mean square combination of arbitrary number of correlated estimates which is also derived. The equation for error covariance characterizing the mean-square accuracy of the new filter is derived. In consequence of parallel structure of the filtering equations the parallel computers can be used for their design. It is shown that this filter is very effective for multisensor systems containing different types of sensors. A practical implementation issue to consider this filter is also addressed. Example demonstrates the accuracy and efficiency of the proposed filter.

Current centralized restoration schemes are unsuitable for the increase of scale and complexity of networks. A novel distributed network partition scheme is proposed in this paper. In this scheme, a large-scale network can be partitioned into some wheellike sub-networks with nuclear nodes. In wheellike sub-networks, ring links and spoke links could provide reciprocal safeguard. Based on such structure, different distributed restoration schemes can be combined for failure restoration. The proposed partition approach has been implemented through computer simulation, and it was tested on practical national-scale optical networks. The simulation result shows that this scheme is practicable and effectual.

In this paper, single-input multiple-output (SIMO)-model-based blind source separation (BSS) is addressed, where unknown mixed source signals are detected at microphones, and can be separated, not into monaural source signals but into SIMO-model-based signals from independent sources as they are at the microphones. This technique is highly applicable to high-fidelity signal processing such as binaural signal processing. First, we provide an experimental comparison between two kinds of SIMO-model-based BSS methods, namely, conventional frequency-domain ICA with projection-back processing (FDICA-PB), and SIMO-ICA which was recently proposed by the authors. Secondly, we propose a new combination technique of the FDICA-PB and SIMO-ICA, which can achieve a higher separation performance than the two methods. The experimental results reveal that the accuracy of the separated SIMO signals in the simple SIMO-ICA is inferior to that of the signals obtained by FDICA-PB under low-quality initial value conditions, but the proposed combination technique can outperform both simple FDICA-PB and SIMO-ICA.

This paper describes techniques of scoring prosodic proficiency of English sentences spoken by Japanese. The multiple regression model predicts the prosodic proficiency using new prosodic measures based on the characteristics of Japanese novice learners of English. Prosodic measures are calculated by comparing prosodic parameters, such as F0, power and duration, of learner's and native speaker's speech. The new measures include the approximation error of the fitting line and the comparison result of prosodic parameters for a limited segment of the word boundary rather than the whole utterance. This paper reveals that the introduction of the new measures improved the correlation by 0.1 between the teachers' and automatic scores.

Spontaneously spoken Japanese includes a lot of grammatically ill-formed linguistic phenomena such as fillers, hesitations, inversions, and so on, which do not appear in written language. This paper proposes a novel method of robust dependency parsing using a large-scale spoken language corpus, and evaluates the availability and robustness of the method using spontaneously spoken dialogue sentences. By utilizing stochastic information about the appearance of ill-formed phenomena, the method can robustly parse spoken Japanese including fillers, inversions, or dependencies over utterance units. Experimental results reveal that the parsing accuracy reached 87.0%, and we confirmed that it is effective to utilize the location information of a bunsetsu, and the distance information between bunsetsus as stochastic information.