This paper provides a computational method to construct a Lyapunov function to prove a stability of hybrid automata that can have nonlinear vector fields. Algebraic inequalities and equations are formulated, which are solved via LMI optimization. Numerical examples are presented to illustrate the proposed method.

This paper addresses the scheduling problem of a class of automated manufacturing systems with multiple resource requests. In the automated manufacturing system model, a set of jobs is to be processed and each job requires a sequence of operations. Each operation may need more than one resource type and multiple identical units with the same resource type. Upon the completion of an operation, resources needed in the next operation of the same job cannot be released and the remaining resources cannot be released until the start of the next operation. The scheduling problem is formulated by Timed Petri nets model under which the scheduling goal consists in sequencing the transition firing sequence in order to avoid the deadlock situation and to minimize the makespan. In the proposed genetic algorithm with deadlock-free constraint, Petri net transition sequence is coded and a deadlock detection method based on D-siphon technology is proposed to reschedule the sequence of transitions. The enabled transitions should be fired as early as possible and thus the quality of solutions can be improved. In the fitness computation procedure, a penalty item for the infeasible solution is involved to prevent the search process from converging to the infeasible solution. The method proposed in this paper can get a feasible scheduling strategy as well as enable the system to achieve good performance. Numerical results presented in the paper show the efficiency of the proposed algorithm.

In this paper, we propose a formal method for detection of three automation surprises in human-machine interaction; a mode confusion, a refusal state, and a blocking state. The mode confusion arises when a machine is in a different mode from that anticipated by the user, and is the most famous automation surprise. The refusal state is a situation that the machine does not respond to a command the user executes. The blocking state is a situation where an internal event occurs, leading to change of an interface the user does not know. In order to detect these phenomena, we propose a composite model in which a machine and a user model evolve concurrently. We show that the detection of these phenomena in human-machine interaction can be reduced to a reachability problem in the composite model.

The three major failures of electrical contacts for automotive relay applications are: contact welding (or contact sticking), high contact resistance and severe contact erosion due to switching arcing. With the demand of high power and multiple functions of automotive vehicles, the switching current has be dramatically increased, it results in higher failing rate, in particular for contact welding. On the other hand, the miniaturization of electromechanical relays has lead to the reduction of mechanical spring force. This not only results in the earlier contact welding but also makes the relay more susceptible to the contact resistance and arc erosion failures. This paper is a review of most recent studies on these three failure aspects. It describes the progress in the understanding of contact welding caused by short arcing and high contact resistance due to contamination of particles and films in relay manufacturing process and also it review the material transfer due to switching arcing. At the end, the brief considerations of electromechanical relays used in 42 volts have also been given.

Subgraph isomorphism problems have various important applications, while generally being NP-complete. Though Ullmann and Konishi proposed the custom circuit designs to accelerate subgraph isomorphism problem, they require many hardware resources for large problems. This study describes the design of data-dependent circuits for subgraph isomorphism problem with evaluation results on an actual FPGA platform. Data-dependent circuits are logic circuits specialized in specific input data. Such circuits are smaller and faster than the original circuit, although it is not reusable and involves circuit generation for each input. In the present study, the circuits were implemented on Xilinx XC2V3000 FPGA, and they successfully operated at a clock frequency 25 MHz. In the case of graphs with 16 vertices, the average execution time is about 7.0% of the software executed on an up-to-date microprocessor (Athlon XP 2600+ of 2.1 GHz clock). Even if the circuit generation time is included, data-dependent circuits are about 14.4 times faster than the software (for random graphs with 16 vertices). This performance advantage becomes larger for larger graphs. Two algorithms (Ullmann's and Konishi's) were examined, and the data-dependent approach was found to be equally effective for both algorithms. We also examined two types of input graph sets, and found that the data-dependent approach shows advantage in both cases.

Recently, broadband access is widely spreading, and many broadband network E-commerce services are planned and developed. This article proposes a broadband online shop where a videoconferencing system is used to enable direct, face-to-face communication. It is important for a broadband online shop to understand what preference their customers want in order to provide them with more appropriate information. By using customer preferences, a salesclerk can have a serviceable conversation with few questions to his online customers. So, we are developing a visual Customer Relationship Management system (v-CRM system) that offers customer preferences to broadband network service such as broadband online shop. In this paper, we classify customer preferences, and describe three visualization methods that enable customer preferences to be intuitively understood quickly. We outline the v-CRM evaluation system and describe an experiment where we evaluated how accurately customer preferences can be recognized using these methods. The results show that v-CRM system is effective for understanding customer preferences.

Techniques for automatic program recognition, at the algorithmic level, could be of high interest for the area of Software Maintenance, in particular for knowledge based reengineering, because the selection of suitable restructuring strategies is mainly driven by algorithmic features of the code. In this paper an automated hierarchical concept parsing recognition technique, and a formalism for the specification of algorithmic concepts, is presented. Based on this technique, the design and development of ALCOR, a production rule based system for automatic recognition of algorithmic concepts within programs, aimed at support of knowledge based reengineering for high performance, is presented.

In this letter we suggest sets of features to classify genres of web documents. Web documents are different from textual documents in that they contain URL and HTML tags within the pages. We introduce the features specific to web documents, which are extracted from URL and HTML tags. Experimental results enable us to evaluate their characteristics and performances. On the basis of the experimental results, we implement a user interface of a web search engine that presents documents grouped by genres.

A compact low-voltage CMOS exponential current-to-voltage converter free from transconductance parameter matching between NMOS and PMOS is proposed. The circuit is composed of level shift circuits and current mirrors. The SPICE simulation results show a 27 dB linear range with a linearity error of less than 1 dB.

This paper is focused on the measurement of the complex permittivity of a liquid phantom by the transmission line method using a coaxial line for measuring high-permittivity and high-loss materials. First, the complex permittivity of the liquid phantom material is measured under various physical lengths of the coaxial line for accurate measurement. Secondly, comparison between the measured result and the result obtained by the coaxial probe method is carried out in the frequency range from 0.5 to 3 GHz. Finally, the measurement error included in the complex permittivity is estimated quantitatively. The discussions lead to the conclusion that accurate measurement of the liquid material with high-permittivity and high-loss is possible by the presented method.

In this work, a simple method for extracting MOSFET threshold voltage, effective channel length and channel mobility by using S-parameter measurement is presented. In the new method, the dependence between the channel conductivity and applied gate voltage of the MOSFET device is cleverly utilized to extract the threshold voltage, while biasing the drain node of the device at zero voltage during measurement. Moreover, the effective channel length and channel mobility can also be obtained with the same measurement. Furthermore, all the physical parameters can be extracted directly on the modeling devices without relying on specifically designed test devices. Most important of all, only one S-parameter measurement is required for each device under test (DUT), making the proposed extraction method promising for automatic measurement applications.

This paper investigates some fundamental properties of one-way alternating pushdown automata with sublinear space. We first show that one-way nondeterministic pushdown automata are incomparale with one-way alternating pushdown automata with only universal states, for spaces between log log n and log n, and also for spaces between log n and n/log n. We then show that there exists an infinite space hierarchy among one-way alternating pushdown automata with only universal states which have sublinear space.

In this paper, we propose a noise-robust automatic speech recognition system that uses orthogonalized distinctive phonetic features (DPFs) as input of HMM with diagonal covariance. In an orthogonalized DPF extraction stage, first, a speech signal is converted to acoustic features composed of local features (LFs) and ΔP, then a multilayer neural network (MLN) with 153 output units composed of context-dependent DPFs of a preceding context DPF vector, a current DPF vector, and a following context DPF vector maps the LFs to DPFs. Karhunen-Loeve transform (KLT) is then applied to orthogonalize each DPF vector in the context-dependent DPFs, using orthogonal bases calculated from a DPF vector that represents 38 Japanese phonemes. Each orthogonalized DPF vector is finally decorrelated one another by using Gram-Schmidt orthogonalization procedure. In experiments, after evaluating the parameters of the MLN input and output units in the DPF extractor, the orthogonalized DPFs are compared with original DPFs. The orthogonalized DPFs are then evaluated in comparison with a standard parameter set of MFCCs and dynamic features. Next, noise robustness is tested using four types of additive noise. The experimental results show that the use of the proposed orthogonalized DPFs can significantly reduce the error rate in an isolated spoken-word recognition task both with clean speech and with speech contaminated by additive noise. Furthermore, we achieved significant improvements when combining the orthogonalized DPFs with conventional static MFCCs and ΔP.

Watson-Crick automata, recently introduced in, are new types of automata in the DNA computing framework, working on tapes which are double stranded sequences of symbols related by a complementarity relation, similar to a DNA molecule. The automata scan separately each of the two strands in a corelated mannar. Some restricted variants of them were also introduced and the relationship between the families of languages recognized by them were investigated in. In this paper, we clarify some relations between the families of languages recognized by the restricted variants of Watson-Crick finite automata and the families in the Chomsky hierarchy.

The model for the process of F0 contour generation, first proposed by Fujisaki and his coworkers, has been successfully applied to Standard Chinese, which is a typical tone language with a distinct feature that both positive and negative tone commands are required. However, the inverse problem, viz., automatic derivation of the model parameters from an observed F0 contour of speech, cannot be solved analytically. Moreover, the extraction of model parameters for Standard Chinese is more difficult than for Japanese and English, because the polarity of tone commands cannot be inferred directly from the F0 contour itself. In this paper, an efficient method is proposed to solve the problem by using information on syllable timing and tone labels. With the same framework as for the successive approximation method proposed for Japanese and English, the method presented here for Standard Chinese is focused on the first-order estimation of tone command parameters. A set of intra-syllable and inter-syllable rules are constructed to recognize the tone command patterns within each syllable. The experiment shows that the method works effectively and gives results comparable to those obtained by manual analysis.

Learning behaviors of hierarchically structured stochastic automata operating in a general nonstationary multiteacher environment are considered. It is shown that convergence with probability 1 to the optimal path is ensured by a new learning algorithm which is an extended form of the relative reward strength algorithm. Several computer simulation results confirm the effectiveness of the proposed algorithm.

The main purpose of this paper is to show that we can exploit the difference (l1-norm and l2-norm) in the probability calculation between quantum and probabilistic computations to claim the difference in their space efficiencies. It is shown that there is a finite language L which contains sentences of length up to O(nc+1) such that: (i) There is a one-way quantum finite automaton (qfa) of O(nc+4) states which recognizes L. (ii) However, if we try to simulate this qfa by a probabilistic finite automaton (pfa) using the same algorithm, then it needs Ω(n2c+4) states. It should be noted that we do not prove real lower bounds for pfa's but show that if pfa's and qfa's use exactly the same algorithm, then qfa's need much less states.

The alternating variant of the shrinking two-pushdown automaton of Buntrock and Otto (1998) is introduced. It is shown that the class of languages accepted by these automata is contained in the class of deterministic context-sensitive languages, and that it contains a PSPACE-complete language. Hence, the closure of this class of languages under log-space reductions coincides with the complexity class PSPACE.

The capabilities of reliable computations in one-dimensional cellular automata are investigated by means of the Early Bird Problem. The problem is typical for situations in massively parallel systems where a global behavior must be achieved by only local interactions between the single elements. The cells that cause the misoperations are assumed to behave as follows. They run a self-diagnosis before the actual computation once. The result is stored locally such that the working state of a cell becomes visible to its neighbors. A non-working (defective) cell cannot modify information but is able to transmit it unchanged with unit speed. We present an O(n log (n) log (n))-time fault-tolerant solution of the Early Bird Problem.

A number-conserving cellular automaton (NCCA) is a cellular automaton (CA) such that all states of cells are represented by integers and the sum of the cell states is conserved throughout its computing process. It can be thought of as a kind of modelization of the physical conservation law of mass or energy. It is known that the local function of a two-dimensional 45-degree reflection-symmetric von Neumann neighbor NCCA can be represented by linear combinations of a binary function. In spite of the number-conserving constraints, it is possible to design an NCCA with complex rules by employing this representation. In this paper, we study the case in which the binary function depends only on the difference of two cell states, i.e., the case in which the function can be regarded as a unary one and its circuit for applying rules to a cell only need adders and a single value table look up module. Even under this constraint, it is possible to construct a logically universal NCCA.