Petri net is a mathematical model for concurrent systems. Liveness is one of important properties of Petri net. Liveness problem of general Petri net is of exponential space complexity and subclasses are suggested with less computational complexity. It is well known that liveness problem of bounded (extended) free choice net is solved in deterministic polynomial time. This paper treats liveness problem of AC/DC nets. AC/DC net is a subclass of Petri net that exhibits no confusion (mixture of concurrency and conflict). This class properly includes the class of free choice nets. It is shown that every minimal siphon of an AC/DC net is trap if and only if every strongly connected siphon is a trap. This result shows that monotone liveness of bounded AC/DC net is solved in deterministic polynomial time. It is shown that this result is true of bounded time AC/DC net with static fair condition.

Recently, an efficient algorithm has been proposed for finding all solutions of systems of nonlinear equations using inverses of approximate Jacobian matrices. In this letter, an effective technique is proposed for improving the computational efficiency of the algorithm with a little bit of computational effort.

There exist some results showing that quantum communications are more powerful than classical communications. Moreover, although quantum entangled states do not give extra information, by using prior entanglement the quantum communication complexity of some functions is less than the classical communication complexity. The communications with prior entanglement can be regarded as a type of public coin models. In this paper, we investigate quantum communications for multi-party with prior entanglement, and show that there exists a generalized inner product function for k-party such that the quantum communication complexity is at most k bits, but the classical communication complexity needs at least 3k/2 bits. Moreover, we also provide a generalized form of prior entanglements that is effective in order to compute some type of Boolean functions.

A VLIW (Very Long Instruction Word) architecture with a new code compaction method has been proposed. For a 3D-geometry processor, we consider two types of 2-issue VLIW architectures, the floating-point execution accelerating VLIW (FP-VLIW) and the data-move enhancing VLIW (MV-VLIW) architectures, as expansions of a Single-Streaming Single Instruction, Multiple Data (SS-SIMD) architecture. To solve the code bloat problem which is common to VLIW architectures, the proposed method makes it possible to compact original codes into the VLIW codes by software tools and decompact the VLIW codes by a simple hardware decompactor composed of an instruction swap circuit on a chip. Speeds and code densities of the two VLIWs with the code compaction are compared to the SS-SIMD with the same instruction set and the same building blocks. The FP-VLIW shows the fastest speed performance in the evaluation results of the viewperf CDRS-03 benchmark programs. It is 36% faster than the SS-SIMD used as reference. The proposed compaction method keeps the 95% code density of the SS-SIMD. One test program shows that the code density of the MV-VLIW is higher than that of the SS-SIMD. This result demonstrates that the merit of compacting nops can be greater than the VLIW penalty. The FP-VLIW architecture with the code compaction achieves 1.36 times the speed performance without significant code-density deterioration.

An advanced spare-connection scheme for K-out-of-N redundancy is proposed for constructing fault-tolerant ring- or toroidal mesh-connected processing-node arrays able to enhance emulation of binary hypercubes by using bypass networks. With this scheme, a component redundancy configuration for a base array with a fixed number of primary nodes, such as that for 8-node ring or 32-node toroidal mesh, can be constructed by using bypass links with a segmented bus structure to selectively connect the primary nodes to a spare node in parallel. These bypass links are allocated to the primary nodes by graph-node coloring with a minimum inter-node distance of three in order to use the bypass links as the hypercube connections as well as to attain strong fault tolerance for reconfiguring the base array with the primary network topology. An extended redundancy configuration for a large fault-tolerant array can be constructed by connecting the component configurations by using external switches of a hub type provided at the bus nodes of the bypass links. This configuration has a network topology of the parallel star-connections of sub-hypercubes whose diameter is smaller than that of the regular hypercube.

The heterogeneous autonomous decentralized system technology offers a way to integrate different types of context-related autonomous decentralized (sub) systems into a coherent system. The aim of this research is to model and evaluate the communication capacity among the subsystems connected by communication gateways of a heterogeneous autonomous decentralized system. Failures of subsystems and communication gateways in the system are taken into account. We use graphs to represent the topologies of heterogeneous autonomous decentralized systems and use the residual connectedness reliability (RCR) to characterize the communication capacity among its subsystems connected by its gateways. This model enables us to share research results obtained in residual connectedness reliability study in graph theory. Not to our surprise, we learnt soon that computing RCR of general graphs is NP-hard. But to our surprise, there exist no efficient approximation algorithms that can give a good estimation of RCR for an arbitrary graph when both vertices and edges may fail. We proposed in this paper a simulation scheme that gave us good results for small to large graphs but failed for very large graphs. Then we applied a theoretical bounding approach. We obtained expressions for upper and lower bounds of RCR for arbitrary graphs. Both upper and lower bound expressions can be computed in polynomial time. We applied these expressions to several typical graphs and showed that the differences between the upper and lower bounds tend to zero as the sizes of graphs tend to infinite. The contributions of this research are twofold, we find an efficient way to model and evaluate the communication capacity of heterogeneous autonomous decentralized systems; we contribute an efficient algorithm to estimate RCR in general graph theory.

This paper presents a new adaptive blind separation of sources (BSS) method for linear and non-linear mixtures. The sources are assumed to be statistically independent with non-uniform and symmetrical PDF. The algorithm is based on both simulated annealing and density estimation methods using a neural network. Considering the properties of the vectorial spaces of sources and mixtures, and using some linearization in the mixture space, the new method is derived. Finally, the main characteristics of the method are simplicity and the fast convergence experimentally validated by the separation of many kinds of signals, such as speech or biomedical data.

Characteristics of the optical feedback noise in semiconductor lasers under superposition of the HF (High Frequency) current were experimentally examined and theoretically analyzed. The feedback noise was mostly suppressed by superposition of HF current, but still remained when frequency of the HF current coincided with a rational number of the round trip time period for the optical feedback in experimental measurement. Theoretical analysis was also given to explain these characteristic based on the mode competition theory of the semiconductor laser.

The temperature compensation technique of InGaP/GaAs power heterojunction bipolar transistor (HBT) with novel bias circuit using Schottky diodes has been developed. The variation in the quiescent current to the temperature is less than 30% from -30C to 90C by this technique, where that is about 125% by the conventional bias circuit. The RF performance of the power HBT MMIC with novel bias circuit shows flat temperature characteristics enough to be used for power application of wireless communications.

The imprecise computation is one of the promising schemes in the real time systems to adapt quality of computations to change of load with keeping the deadlines of tasks in the systems. When overload occurs in the systems, the minimum requirements on the deadline are assured by decreasing quality of the computation. This paper describes how to apply the concept of the imprecise computation to automobile control in the expressway assuming the intelligent transportation system (shortly, ITS). The deadline violation of tasks for automobile control in the expressway induces collision of automobiles. Regardless of whether the expressway is congested or not, collision of automobiles must be avoided. To satisfy such requirement, the concept of the imprecise computation is effective. This paper proposes an adaptive scheduling using the imprecise computation to avoid collision of automobiles and increase throughput, and shows results of simulation experiments about an adaptive scheduling for automobiles control.

In the theory of average-case NP-completeness, Levin introduced the polynomial domination and Gurevich did the average polynomial domination. Ben-David et al. proved that if P-samp (the class of polynomial-time samplable distributions) is polynomially dominated by P-comp (the class of polynomial-time computable distributions) then there exists no strong one-way function. This result will be strengthened by relaxing the assumption from the polynomial domination to the average polynomial domination. Our results also include incompleteness for average polynomial-time one-one reducibility from (NP,P-samp) to (NP,P-comp). To derive these and other related results, a prefix-search algorithm presented by Ben-David et al. will be modified to survive the average polynomial domination.

Analysis of electromagnetic wave propagation and scattering in a random medium is a field of great interest. This research field becomes more important if we consider the study of phsyical effects on wave propagation and scattering from targets in random media. Curvature of the targets' cross-sections plays an important parameter in the radar detection problem. In previous study, analysis of scattering data from nonconvex conducting targets has pointed out to the effect of target configuration together with both effects of the spatial coherence length of incident waves around the target and the double passage on the backscattering enhancement. Here, we make sure this fact by considering targets with relatively large sizes in continuous random media for H-wave incidence. We assume the cross-section of targets to be smoothly deformed contour comprising concave and convex portions.

We studied a three-wave coupling process occurring in microwave power transmission (MPT) experiment in the ionospheric plasma by performing computer experiments with one-dimensional electromagnetic PIC (Particle-In-Cell) model. In order to examine the spatial variation of the coupling process, we continuously emitted intense electromagnetic wave from an antenna located at a simulation boundary. In the three-wave coupling, a low-frequency electrostatic wave is excited as the consequence of a nonlinear interaction between the forward propagating pump wave and backscattered one. In the computer experiments, low-frequency electrostatic bursts are discontinuously observed in space. The discontinuity of the electrostatic bursts is accounted for by the local electron heating due to the bursts and associated modification of the wave dispersion relation. In a case where the pump wave propagates along the geomagnetic field Bext, several bursts of Langmuir waves are observed. Since the first burst consumes a part of the pump wave energy, the pump wave is weakened and cannot trigger the three-wave coupling beyond the region where the burst occurs. Since the dispersion relation of the Langmuir wave is variable due to the local electron heating by the burst, the coupling condition eventually becomes unsatisfied and the first interaction becomes weak. Another burst of Langmuir waves is observed at a different region beyond the location of the first burst. In the case of perpendicular propagation, the upper hybrid wave, one of the mode branches of the electron cyclotron harmonic waves, is excited. Since the dispersion relation of the upper hybrid wave is less sensitive to the electron temperature, the coupling condition is not easily violated by the temperature increase. As a result, the three-wave coupling periodically takes place in time and eventually the transmission ratio of the microwaves becomes approximately 20% while almost no attenuation of the pump waves is observed after the first electrostatic burst in the parallel case.

Most of the current research is focused on the row-column scanning keyboard interface for English letter and number input. At the present time, there are insufficient methods to control the computer mouse effectively. In this study, a categorized row-column scanning computer interface is developed to improve the conventional single key-in row-column scanning method. The beneficial developments include: speed enhancement by categorizing radicals of keyboard, input control of mouse, and multiple selection of input methods such as surface electromyographic (SEMG) control, breath pressure sensibility control with puff, force sensibility control, infrared sensibility control and single key-in control. Meanwhile, an enhancement software package is developed to increase the row-column scanning keyboard capabilities and to upgrade the completeness of the computer mouse for the disabled persons to control the operation of data entry and the associated implementation better.

Network caches reduce network traffic as well as user response time. When implementing network caches, the object replacement problem is one of the core problems; The problem is to determine which objects should be evicted from a cache when there is insufficient space. This paper first formalizes the problem and gives a simple but sufficient condition for deterministic online algorithms to be competitive. Based on the condition, a general framework to make a non-competitive algorithm competitive is constructed. As an application of the framework, an online algorithm, called Competitive_SIZE, is proposed. Both event-driven and trace-driven simulations show that Competitive_SIZE is better than previously proposed algorithms such as LRU (Least Recently Used).

In this paper, we shall construct mathematical theory based on the concept of set-valued mappings, suitable for available operation of network systems extraordinarily complicated and diversified on large scales. Fundamental conditions for availability of system behaviors of such network systems are clarified in a form of fixed point theorem for system of set-valued mappings.

We often see reflection phenomenon in our life. For example, through window glass, we can see real objects, but reflection causes virtual objects to appear in front of the glass. Thus, it is sometimes difficult to recognize the real objects. Some works have been proposed to separate these real and virtual objects using an optical property called polarization. However, they have a restriction on one assumption: the angle of incidence. In this paper, we overcome this difficulty using independent component analysis (ICA). We show the efficiency of the proposed method, by experimental results.

Digital signal processors (DSPs) usually employ indirect addressing using address registers (ARs) to indicate their memory addresses, which often introduces overhead codes in AR updates for next memory accesses. Reduction of such overhead code is one of the important issues in automatic generation of highly-efficient DSP codes. In this paper, a new automatic address allocation method incorpolated with computational order rearrangement at local commutative parts is proposed. The method formulates a given memory access sequence by a graph representation, where several strategies to handle freedom in memory access orders at the computational commutative parts are introduced and examined. A compiler scheme is also extended such that computational order at the commutative parts is rearranged according to the derived memory allocation. The proposed methods are applied to an existing DSP compiler for µPD77230(NEC), and codes generated for several examples are compared with memory allocations by the conventional methods.

In this paper, we propose an ECG waveform compression technique based on the matching pursuit. The matching pursuit is an iterative non-orthogonal signal expansion technique. A signal is decomposed to atoms in a function dictionary. The constraint to the dictionary is only the over-completeness to signals. The function dictionary can be defined to be best match to the structure of the ECG waveform. In this paper, we introduce the multiscale analysis to the implementation of inner product computations between signals and atoms in the matching pursuit iteration. The computational cost can be reduced by utilization of the filter bank of the multiscale analysis. We show the waveform approximation capability of the matching pursuit with multiscale analysis. We show that a simple 4-tap integer filter bank is enough to the approximation and compression of ECG waveforms. In ECG waveform compression, we apply the error feed-back procedure to the matching pursuit iteration to reduce the norm of the approximation error. Finally, actual ECG waveform compression by the proposed method are demonstrated. The proposed method achieve the compression by the factor 10 to 30. The compression ratio given by the proposed method is higher than the orthogonal wavelet transform coding in the range of the reconstruction precision lower than 9% in PRD.

In this paper, we deal with the problem of compatibility class encoding, and propose a novel algorithm for finding a good functional decomposition with application to LUT-based FPGA synthesis. Based on exploration of the design space, we concentrate on extracting a set of components, which can be merged into the minimum number of multiple-output CLBs or LUTs, such that the decomposition constructed from these components is also minimal. In particular, to explore more degrees of freedom, we introduce pliable encoding to take over the conventional rigid encoding when it fails to find a satisfactory decomposition by rigid encoding. Experimental results on a large set of MCNC91 logic synthesis benchmarks show that our method is quite promising.