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.

Many P2P lookup services based on distributed hash tables (DHT) have appeared recently. These schemes are built upon overlay networks and ignore distance to the target resources. As a result, P2P lookups often suffer from unnecessarily long routes in the underlay network, which we call overlay dilation. This paper proposes a new scheme for resource routing, called hybrid hierarchical overlay routing, dubbed Hyho. We introduce distance-weighted Bloom filters (dwBFs) as a concise representation of routing information for scattered resources in overlay networks. To further reduce the size of Bloom filters, so that they are linear in the number of distinct resources, Hyho splits overlay networks in accordance with DHT, where each subnetwork has a smaller set of resources and spans the entire network thinly. As a result, Hyho constructs a hierarchical overlay network and routes requests accordingly. Simulation results show that Hyho can reduce overlay dilation to one half that yielded by the Chord lookup service.

This paper proposes a cell layout synthesis method via Boolean Satisfiability (SAT). Cell layout synthesis problems are first transformed into SAT problems by our formulations. Our method realizes a high-speed layout synthesis for CMOS logic cells and guarantees to generate the minimum-width cells with routability under our layout styles. It considers complementary P-/N-MOSFETs individually during transistor placement, and can generate smaller width layout compared with pairing the complementary P-/N-MOSFETs case. To demonstrate the effectiveness of our SAT-based cell synthesis, we present experimental results which compare it with the 0-1 ILP-based transistor placement method and a commercial cell generation tool. The experimental results show that our SAT-based method can generate minimum-width placements in much shorter run time than the 0-1 ILP-based transistor placement method, and can generate the cell layouts of 32 static dual CMOS logic circuits in 54% run time compared with the commercial tool. Area increase of our method without compaction is only 3% compared with the commercial tool with compaction.

This paper proposes a scalable video delivery scheme, named P2PVD, for large-scale video-on-demand applications based on the emerging peer-to-peer structure and characteristic user behaviors. Two types of orders are permitted in P2PVD: reserved and urgent. Reserved orders are encouraged with a lower price policy, which smoothes the network traffic and reduces the server load. The requesting peers use delay-aware dynamic parallel transmission to serve the reserved and urgent orders, and supplying peers employ three priority rules to increase the capacity of P2PVD. Experimental results indicate that P2PVD is scalable.

With the need and adoption of link aggregation where multiple links exist between two adjacent nodes in order to increase transmission capacity between them, there arise the problems of service guarantee and fair sharing of multiple servers. Although a lot of significant work has been done for single-server scheduling disciplines in the past years, not much work is available for multi-server scheduling disciplines. In this paper, we present and investigate two round robin based multi-server scheduling disciplines, which are Multi-Server Uniform Round Robin (MS-URR) and Multi-Server Deficit Round Robin (MS-DRR). In particular, we analyze their service guarantees and fairness bounds. In addition, we discuss the misordering problem with MS-DRR and present a bound for its misordering probability.

This paper presents a dual-frequency microstrip antenna for both 2 GHz and 5 GHz for a dual-band receiver. For a simple structure and low cost design, the microstrip feed circuit is designed on the same substrate as the antenna elements. Each antenna element is directly fed by the microstrip line, and the open stubs are loaded on the feed line of 2 GHz to suppress the higher order mode resonances between 2 GHz and 5 GHz. The feed line length of each antenna is adjusted so as to change it to the open condition at the other element frequency at the feed point. In addition, we propose the antenna structure in which two antenna elements for 2 GHz are split and placed at either sides of the 5 GHz antenna to coincide with the center positions of each antenna element. We investigate the proposed antenna by calculations and measurements to show the combiner free design for the dual band antenna.

In this paper, we consider a data mining problem for semi-structured data. Modeling semi-structured data as labeled ordered trees, we present an efficient algorithm for discovering frequent substructures from a large collection of semi-structured data. By extending the enumeration technique developed by Bayardo (SIGMOD'98) for discovering long itemsets, our algorithm scales almost linearly in the total size of maximal tree patterns contained in an input collection depending mildly on the size of the longest pattern. We also developed several pruning techniques that significantly speed-up the search. Experiments on Web data show that our algorithm runs efficiently on real-life datasets combined with proposed pruning techniques in the wide range of parameters.

Availability of network access "anytime and anywhere" will impose new requirements to presence services - server load sharing and privacy protection. In such cases, presence services would have to deal with sensor device information with maximum consideration of user's privacy. In this paper, we propose FieldCast: peer-to-peer system architecture for presence information exchange in ubiquitous computing environment. According to our proposal, presence information is exchanged directly among user's own computing resources. We illustrate our result of evaluation that proves the feasibility of our proposal.

This paper introduces the problem of n mobile agents that repeatedly visit all n nodes of a given network, subject to the constraint that no two agents can simultaneously occupy a node. This paper first presents a self-stabilizing phase-based protocol for a tree network on a synchronous model. The protocol realizes agent traversal with O(Δn) time where n is the number of nodes and Δ is the maximum degree of any vertex in the communication network. The phase-based protocol can also be applied to an asynchronous model and a ring network. This paper also presents a self-stabilizing link-alternator-based protocol with agent traversal time of O(Δn) for a tree network on an asynchronous model. The protocols are proved to be asymptotically optimal with respect to the agent traversal time.

The massively multiplayer online game (MMOG) industry is suffering from huge outgoing traffic from centralized servers. To accommodate this traffic, game companies claim large bandwidth to Internet Data Centers (IDCs), and several months' payment for that bandwidth is likely to even exceed the cost for MMOG servers. In this paper, we propose a MMOG server architecture to reduce outgoing bandwidth consumption from MMOG servers. The proposed architecture distributes some functions of servers to selected clients, and those clients are in charge of event notification to other clients in order to reduce the outgoing traffic from servers. The clients with server functions communicate with each other in peer-to-peer manner. We analyze traffic reduction as a function of cell-daemonable ratio of clients, and the results show that up to 80% of outgoing traffic from servers can be reduced using the proposed architecture when 10% of clients are cell-daemonable.

The most important function of a router is to perform IP lookup that determines the output ports of incoming IP packets by their destination addresses. Hence, IP lookup is one of the main issues in implementing high-speed routers. The IP lookup algorithm implemented in IQ2200 Chipset with two-level table architecture can efficiently use memory. However, it wastes processor resource for full re-construction of the forwarding tables whenever every route insertion/deletion is requested. In order to improve the utilization of processor resource, we propose an IP lookup algorithm with three-level table architecture for high-speed routers. We evaluate the performance of the proposed algorithm in terms of the memory size required for storing lookup information and the number of memory access in constructing forwarding tables. Being compared with the IQ2200 scheme, the proposed scheme can reduce the number of memory access up to 99% even though it needs about 16% more memory.

In this paper, a novel type of the step-up high frequency transformer linked full-bridge soft-switching phase-shift PWM DC-DC power converter with ZVS and ZCS bridge legs is proposed for small scale fuel cell power generation systems, automotive AC power supplies. A tapped inductor filter with a freewheeling diode is implemented in the proposed soft-switching DC-DC power converter to minimize the circulating current in the high-frequency step-up transformer primary side and high-frequency inverter stage. Using a tapped inductor filter with a freewheeling diode makes possible to reduce the circulating current without any active switches and theirs gate-drive circuits. The operating principle of the proposed DC-DC power converter with each operation mode during a half cycle of the steady state operation is explained. The optimum design of the tapped inductor turns ratio is described on the basis of the circuit simulation results. Developing 1 kW 100 kHz prototype with power MOSFETs and 36 V DC source verifies the practical effectiveness of the proposed soft-switching DC-DC power converter. The actual efficiency of the proposed DC-DC power converter is obtained 94% for the wide load and output voltage variation ranges.

This paper presents the definition and implementation design of a low power data bus encoding scheme dedicated to system on chip video architectures. Trends in CMOS technologies focus the attention on the energy consumption issue related to on-chip global communication; this is especially true for data dominated applications such as video processing. Taking into account scaling effects a novel coupling-aware bus power model is used to investigate the statistical properties of video data collected in the system bus of a reference hardware/software H.263/MPEG-4 video coder architecture. The results of this analysis and the low complexity requirements drive the definition of a bus encoding scheme called CDSPBI (Coupling Driven Separated Partial Bus Invert), optimized ad-hoc for video data. A VLSI implementation of the coding circuits completes the work with an area/delay/power characterization that shows the effectiveness of the proposed scheme in terms of global power saving for a small circuit area overhead.

This paper describes an approach to feature extraction in speech recognition systems using kernel principal component analysis (KPCA). This approach represents speech features as the projection of the mel-cepstral coefficients mapped into a feature space via a non-linear mapping onto the principal components. The non-linear mapping is implicitly performed using the kernel-trick, which is a useful way of not mapping the input space into a feature space explicitly, making this mapping computationally feasible. It is shown that the application of dynamic (Δ) and acceleration (ΔΔ) coefficients, before and/or after the KPCA feature extraction procedure, is essential in order to obtain higher classification performance. Better results were obtained by using this approach when compared to the standard technique.

This article introduces a novel approach to model phonology and morphosyntax in morpheme unit-based speech recognizers. The proposed methods are evaluated on a Hungarian newspaper dictation task that requires modeling over 1 million different word forms. The architecture of the recognition system is based on the weighted finite-state transducer (WFST) paradigm. The vocabulary units used in the system are morpheme-based in order to provide sufficient coverage of the large number of word-forms resulting from affixation and compounding. Besides the basic pronunciation model and the morpheme N-gram language model we evaluate a novel phonology model and the novel stochastic morphosyntactic language model (SMLM). Thanks to the flexible transducer-based architecture of the system, these new components are integrated seamlessly with the basic modules with no need to modify the decoder itself. We compare the phoneme, morpheme, and word error-rates as well as the sizes of the recognition networks in two configurations. In one configuration we use only the N-gram model while in the other we use the combined model. The proposed stochastic morphosyntactic language model decreases the morpheme error rate by between 1.7 and 7.2% relatively when compared to the baseline trigram system. The proposed phonology model reduced the error rate by 8.32%. The morpheme error-rate of the best configuration is 18% and the best word error-rate is 22.3%.

This letter presents a practical approach for high-quality built-in test using a test pattern generator called neighborhood pattern generator (NPG). NPG is practical mainly because its structure is independent of circuit under test and it can realize high fault coverage not only for stuck-at faults but also for transition faults. Some techniques are also proposed for further improvement in practical applicability of NPG. Experimental results for large industrial circuits illustrate the efficiency of the proposed approach.

This paper presents a non-scan design scheme to enhance delay fault testability of controllers. In this scheme, we utilize a given state transition graph (STG) to test delay faults in its synthesized controller. The original behavior of the STG is used during test application. For faults that cannot be detected by using the original behavior, we design an extra logic, called an invalid test state and transition generator, to make those faults detectable. Our scheme allows achieving short test application time and at-speed testing. We show the effectiveness of our method by experiments.

A new moment computation technique for general lumped R(L)C interconnect circuits with multiple resistor loops is proposed. Using the concept of tearing, a lumped R(L)C network can be partitioned into a spanning tree and several resistor links. The contributions of network moments from each tree and the corresponding links can be determined independently. By combining the conventional moment computation algorithms and the reduced ordered binary decision diagram (ROBDD), the proposed method can compute system moments efficiently. Experimental results have demonstrate that the proposed method can indeed obtain accurate moments and is more efficient than the conventional approach.

A fully integrated current-steering 10-b CMOS Digital-to-Analog Converter with on-chip terminated resistors is presented. In order to improve the device-mismatching problem of internal termination resistors, a self-calibrated current bias circuit is designed. With the self-calibrated current bias circuit, the gain error of the output voltage swing is reduced within 0.5%. For the purpose of reducing glitch noises, furthermore, a novel current switch based on a deglitching circuit is proposed. The prototype circuit has been fabricated with a 3 V 0.35 µm 2-poly 3-metal CMOS technology, and it occupies 1350 µm750 µm silicon area with 45 mW power consumption. The measured INL and DNL are within 0.5LSB, respectively. The measured SFDR is about 65 dB, when an input signal is about 8 MHz at 100 MHz clock frequency.

The methodologies of product-line engineering emphasize proactive reuse to construct high-quality products more quickly that are less costly. Requirement engineering for software product families differs significantly from requirement engineering for single software products. The requirements for a product line are written for the group of systems as a whole, with requirements for individual systems specified by a delta or an increment to the generic set. Therefore, it is necessary to identify and explicitly denote the regions of commonality and points of variation at the requirement level. In this paper, we suggest a method of producing requirements that will be a core asset in the product line. Briefly, requirements for families of similar systems (i.e. domain) are collected and generalized which are then analyzed and modeled. The domain requirement as a core asset explicitly manages the commonality and variability. Through this method, the reuse of domain requirements can be enhanced. As a result, the cost and time of software development can be reduced and the productivity increased while significantly reducing error in the requirements.