A linear term tree is defined as an edge-labeled rooted tree pattern with ordered children and internal structured variables whose labels are mutually distinct. A variable can be replaced with arbitrary edge-labeled rooted ordered trees. We consider the polynomial time learnability of finite unions of linear term trees in the exact learning model formalized by Angluin. The language L(t) of a linear term tree t is the set of all trees obtained from t by substituting arbitrary edge-labeled rooted ordered trees for all variables in t. Moreover, for a finite set S of linear term trees, we define L(S)=∪t∈S L(t). A target of learning, denoted by T*, is a finite set of linear term trees, where the number of edge labels is infinite. In this paper, for any set T* of m linear term trees (m ≥ 0), we present a query learning algorithm which exactly identifies T* in polynomial time using at most 2mn2 Restricted Subset queries and at most m+1 Equivalence queries, where n is the maximum size of counterexamples. Finally, we note that finite sets of linear term trees are not learnable in polynomial time using Restricted Equivalence, Membership and Subset queries.

Modern applications of pattern recognition generate very large amounts of data, which require large computational effort to process. However, the majority of the methods intended for large-scale problems aim to merely adapt standard classification methods without considering if those algorithms are appropriated for large-scale problems. CombNET-II was one of the first methods specifically proposed for such kind of a task. Recently, an extension of this model, named CombNET-III, was proposed. The main modifications over the previous model was the substitution of the expert networks by Support Vectors Machines (SVM) and the development of a general probabilistic framework. Although the previous model's performance and flexibility were improved, the low accuracy of the gating network was still compromising CombNET-III's classification results. In addition, due to the use of SVM based experts, the computational complexity is higher than CombNET-II. This paper proposes a new two-layered gating network structure that reduces the compromise between number of clusters and accuracy, increasing the model's performance with only a small complexity increase. This high-accuracy gating network also enables the removal the low confidence expert networks from the decoding procedure. This, in addition to a new faster strategy for calculating multiclass SVM outputs significantly reduced the computational complexity. Experimental results of problems with large number of categories show that the proposed model outperforms the original CombNET-III, while presenting a computational complexity more than one order of magnitude smaller. Moreover, when applied to a database with a large number of samples, it outperformed all compared methods, confirming the proposed model's flexibility.

Though machine vision systems for automatically detecting visual defects, called mura, have been developed for thin flat transistor liquid crystal display (TFT-LCD) panels, they have not yet reached a level of reliability which can replace human inspectors. To establish an objective criterion for identifying real defects, some index functions for quantifying defect levels based on human perception have been recently researched. However, while these functions have been verified in the laboratory, further consideration is needed in order to apply them to real systems in the field. To begin with, we should correct the distortion occurring through the capturing of panels. Distortion can cause the defect level in the observed image to differ from that in the panel. There are several known methods to restore the observed image in general vision systems. However, TFT-LCD panel images have a unique background degradation composed of background non-uniformity and vignetting effect which cannot easily be restored through traditional methods. Therefore, in this paper we present a new method to correct background degradation of TFT-LCD panel images using principal component analysis (PCA). Experimental results show that our method properly restores the given observed images and the transformed shape of muras closely approaches the original undistorted shape.

Meeting the tough linearity and noise required by GSM and UMTS receivers in CMOS technology is challenging. A new IIP2 calibration technique based on canceling the second order nonlinearities of mixer, generated in the input RF transistors, is introduced. By using this technique about 22 dB mixer IIP2 improvement is achieved. The proposed calibration circuit can be used in multi-standard mixer because of high bandwidth of the calibration circuitry. Moreover it can work with voltage supplies as low as 1 V. Using this technique a multi-standard mixer supporting PCS, UMTS and IEEE802.11b-g is developed. The design is done in CMOS 65 nm technology with 1.2 V supply while it consumes about 7 mA current.

A high-speed triangular-modulated spread-spectrum clock generator using a fractional phase-locked loop is presented. The fractional division is implemented by a nested fractional topology, which is constructed from a dual-modulus divide-by-(N-1/16)/N divider to divide the VCO outputs as a first division period and a fractional control circuit to establish a second division period to cause the overall fractional division. The dual-modulus divider introduces a delay-locked-loop network to achieve phase compensation. Operating at the frequency of 3.2 GHz, the measured peak power reduction is around 16 dB for a deviation of 0.37% and a frequency modulation of 33 kHz. The circuit occupies 1.41.4 mm2 in a 0.18-µm CMOS process and consumes 52 mW.

This paper deals with redundant 3D mesh processor arrays using 1.5-track switches, considering track and switch faults together with processor faults. Four variants are defined based on the distributions of spare PEs, and arrays of three variants have the same PE redundancies among them, but the fabrication-time costs are different. We investigate in detail how the reliability of a total system changes according to the reliabilities of tracks and switches as well as PEs, and show the concrete values of Mt and Ms, when the reliability of array are almost the same even if its variant is changed, and when it is not so, respectively, where Mt and Ms are the ratio of the hardware complexities of a PE and a track, and that of a PE and a contact point of a switch, respectively. Other results which are effective basis for the design of fault-tolerant 3D PE arrays using 1.5-TSs are given.

A new subfamily of sequences with optimal correlation properties is constructed for the generalized Kasami set. A lower bound on the linear span is established. It is proved that with suitable choices of parameters, this subfamily has exponentially larger linear spans than either No sequences or TN sequences. A class of sequences with ideal autocorrelation is also proved to have large linear span.

Several grammars of which generative power is between context-free grammar and context-sensitive grammar were proposed. Among them are macro grammar and tree adjoining grammar. Multiple context-free grammar is also a natural extension of context-free grammars, and is known to be stronger in its generative power than tree adjoining grammar and yet to be recognizable in polynomial time. In this paper, the generative power of several subclasses of variable-linear macro grammars and that of multiple context-free grammars are compared in details.

In this paper, the effects of Bragg scattering on ultra-wideband (UWB) signal transmission from periodic surfaces are reported. First, the frequency dispersive property of Bragg scattering is theoretically and experimentally confirmed. Next, the transfer function of both specular path and Bragg scattering are extracted. Then direct sequence UWB (DS-UWB) transmission simulations are conducted by using a raised cosine pulse that occupied 3.1 to 10.6 GHz and a Gaussian pulse that occupied 8.75 to 9.25 GHz. Finally, the effects of Bragg scattering on UWB systems are discussed.

The combination of Multiple-Input Multiple-Output (MIMO) and Orthogonal Frequency Division Multiplexing (OFDM) technologies gives wireless communications systems the advantages of lower bit error rate (BER) and higher data rate in frequency-selective fading environments. However, the main drawbacks of MIMO systems are their high complexity and high cost. Therefore, antenna selection in MIMO systems has been shown to be an effective way to overcome the drawbacks. In this paper, we propose two receive antenna selection methods for a MIMO-OFDM system with radio frequency (RF) switches and polarization antenna elements at the receiver side, taking into consideration low computational complexity. The first method selects a set of polarization antenna elements which gives lower correlation between received signals and larger received signal power, thus achieves a lower BER with low computational complexity. The second method first selects a set of polarization antenna elements based on the criterion of the first method and another set of polarization antenna elements based on the criterion of minimizing the correlation between the received signals; it then calculates the signal-to-interference-plus-noise power ratio (SINR) of the two sets and selects a set with larger SINR. As a result, the second method achieves a better BER than the first one but it also requires higher computational complexity than the first one. We use the measured channel data to evaluate the performance of the two methods and show that they work effectively for the realistic channel.

Multi-carrier code division multiple access (MC-CDMA) has been considered as one of the promising techniques for the next generation of mobile communication systems because of its efficient bandwidth usage, robustness to the multi-path fading and simple channel-sharing scheme. However, MC-CDMA cannot be employed in the uplink communication where the transmitted signal from each user propagates through the different multi-path fading channel, and the received signals are no longer orthogonal at the base station. As a result, bit error rate (BER) performance in the uplink MC-CDMA communication would be strongly degraded due to the occurrence of multi-user interference (MUI). To solve the MUI problem in the uplink MC-CDMA, the pre-equalization method was proposed in which the uplink signal is pre-equalized at the user terminal by using the channel response estimated from the downlink. Although the pre-equalization method is very effective for the stationary uplink channel with fixed users, it is hard to be employed in the time varying fading channel with mobile users, because there is a big difference in the channel responses between downlink and uplink. For the efficient MUI compensation, each user terminal would be required to predict the future channel conditions based on the current observation. This paper proposes a method for model based uplink channel response prediction by employing the spectral decomposition of the downlink channel impulse response. Computer simulation results show that the proposed method can achieve the accurate prediction of channel response for mobile users during the uplink transmission and allows the effective MUI compensation.

We describe the transmission characteristics of a wavelength independent wavelength division multiplexing passive optical network (WDM-PON) based on a wavelength channel data rewriter (WCDR). The WCDR is composed of a linear amplifier (LA) and a saturated semiconductor optical amplifier (SOA), and by using the WCDR in optical network units (ONUs), we can erase the downstream signal and modulate the same wavelength channel with the upstream signal. In this paper, we analyze the data rewriting characteristic, the frequency chirp characteristic and the bit error rate (BER) degradation occasioned by the use of saturated SOAs. Furthermore, we report high-speed transmission with power penalty of less than 1 dB at bit rates of 1.25 Gbit/s, 2.5 Gbit/s and 10 Gbit/s for downstream signals and 1.25 Gbit/s for upstream signals after transmission through 40 km of single-mode fiber.

This paper introduces an adaptive low complexity pre-processing filter to improve the coding performance of seriously degraded video sequences that is caused by the additive noise. The additive noise leads to a decrease in coding performance due to the high frequency components. By incorporating local statistics and quantization parameter into filtering process, the spurious noise is significantly attenuated and coding efficiency is improved for given quantization step size. In order to reduce the complexity of the pre-processing filter, the simplified local statistics and quantization parameter are introduced. The simulation results show the capability of the proposed algorithm.

In this Letter, we investigate the correlation rate of a random sequence data set which is collected by RFID (Radio Frequency IDentification) readers in an indoor location. Using a passive RFID tag introduces reading error, which causes a loss of original data. From the question of how sensing errors of RFID readers affect the location prediction algorithm used for context awareness services at home, we analyze the correlation rate of a collected data set with respect to RFID reader-sensing error rate. Through our analysis, we conclude that the prediction accuracy can be better or worse than the one of the original data streams according to the error rate. We suggest that the reader specification has to be satisfied by the error boundary which is found in this work for the tolerant location prediction.

When a store sells items to customers, the store wishes to decide the prices of the items to maximize its profit. If the store sells the items with low (resp. high) prices, the customers buy more (resp. less) items, which provides less profit to the store. It would be hard for the store to decide the prices of items. Assume that a store has a set V of n items and there is a set C of m customers who wish to buy those items. The goal of the store is to decide the price of each item to maximize its profit. We refer to this maximization problem as an item pricing problem. We classify the item pricing problems according to how many items the store can sell or how the customers valuate the items. If the store can sell every item i with unlimited (resp. limited) amount, we refer to this as unlimited supply (resp. limited supply). We say that the item pricing problem is single-minded if each customer j ∈ C wishes to buy a set ej ⊆ V of items and assigns valuation w(ej) ≥ 0. For the single-minded item pricing problems (in unlimited supply), Balcan and Blum regarded them as weighted k-hypergraphs and gave several approximation algorithms. In this paper, we focus on the (pseudo) degree of k-hypergraphs and the valuation ratio, i.e., the ratio between the smallest and the largest valuations. Then for the single-minded item pricing problems (in unlimited supply), we show improved approximation algorithms (for k-hypergraphs, general graphs, bipartite graphs, etc.) with respect to the maximum (pseudo) degree and the valuation ratio.

Due to the proliferation of mobile devices connected to the Internet, implementing a secure and practical Mobile IP has become an important goal. A mobile IP can not work properly without authentication between the mobile node (MN), the home agent (HA) and the foreign agent (FA). In this paper, we propose a practical Mobile IP authentication protocol that uses public key cryptography only during the initial authentication. The proposed scheme is compatible with the conventional Mobile IP protocol and provides scalability against the number of MN's. We also show that the proposed protocol offers secure operation.

We suggest a dual thresholds method for the dynamic bandwidth allocation in EPON. In the suggested method, a buffer in ONU has two thresholds and ONU generates a normal request and a greedy request based on the two thresholds. Also, OLT estimates the overall traffic load and grants the greedy request when estimated traffic is light. We study upstream channel resource wastage and show the suggested method decreases the upstream channel resource wastage. Using simulation, we validate the dual thresholds method is superior to the existing methods in the mean delay.

The historical review of Taiwan's researching activities on the features of PECVD grown SiOx are also included to realize the performance of Si nanocrystal based MOSLED made by such a Si-rich SiOx film with embedded Si nanocrystals on conventional Si substrate. A surface nano-roughened Si substrate with interfacial Si nano-pyramids at SiOx/Si interface are also reviewed, which provide the capabilities of enhancing the surface roughness induced total-internal-reflection relaxation and the Fowler-Nordheim tunneling based carrier injection. These structures enable the light emission and extraction from a metal-SiOx-Si MOSLED.

In this paper, we present a clean and simple formulation of survey propagation (SP) for constraint-satisfaction problems as "probabilistic token passing". The result shows the importance of extending variable alphabets to their power sets in designing SP algorithms.

In this paper, a frequency transformation for designing polyphase transfer functions is proposed. A modification to the bilinear LP-LP transformation, which assigns both stopband edges on negative frequency range whereas passband edges are on positive one, results polyphase transfer functions. Design examples show validity of the proposed method.