A graph G is said to be universal for a family F of graphs if G contains every graph in F as a subgraph. A minimum universal graph for F is a universal graph for F with the minimum number of edges. This paper considers a minimum universal graph for the family F^k_n of graphs on n vertices with path-width at most k. We first show that the number of edges in a universal graph F^k_n is at least Ω(kn log(n/k)). Next, we construct a universal graph for F^k_n with O(kn log(n/k)) edges, and show that the number of edges in a minimum universal graph for F^k_n is Θ(kn log(n/k)) .

Many combinatorial problems can be efficiently solved for partial k-trees (graphs of treewidth bounded by k). The edge-coloring problem is one of the well-known combinatorial problems for which no NC algorithms have been obtained for partial k-trees. This paper gives an optimal and first NC parallel algorithm to find an edge-coloring of any given partial k-tree with bounded degrees using a minimum number of colors. In the paper k is assumed to be bounded.

Complexity of Boolean functions satisfying the propagation criterion (PC), an extended notion of the perfect nonlinearity, is discussed on several computation models. The following topics are investigated: (i) relationships between the unateness and the degree of the PC, (ii) the inversion complexity of perfectly nonlinear Boolean functions, (iii) the formula size of Boolean functions that satisfy the PC of degree 1, (iv) the area-time-square complexity of VLSI circuits computing perfectly nonlinear Boolean functions, (v) the OBDD size perfectly nonlinear Boolean functions.

This paper deals with an efficient radix-2 divider design theory that uses carry-propagation-free adders based on redundant binary{1, 0, 1} representation. In order to compute the division fast, we look ahead to the next step quotient-digit selection embedded in the current partial remainder calculation. The solution is a function of the four most significant digits of the current partial remainder, when scaling the divisor in the range [1, 9/8). In gate depth, this result is better than the higher radix-4 case without the look-ahead quotient-digit selection and the design is simple.

Circuit design techniques for linearizing adaptively biased differential pairs are described. An emitter-and source-coupled pair is adaptively biased by a squaring circuit to linearize its transconductance, one of whose inputs is divided by resistors. An input signal for a differential pair or a squaring circuit is set to an adequate amplitude by a resistive divider without sacrificing linearity. Therefore, a differential pair is biased by the output current of a squaring circuit and they are coupled directly. There are three design techniques for squaring circuits. One is the transistor-size unbalance technique. Another is the bias offset technique. A third is the multitail technique. The bipolar and MOS squaring circuits discussed in this paper were proposed by the author previously, and consist of transistor-pairs with different transistor size (i.e., the emitter areas or gate W/L values are different), transistor-pairs with the same bias offset, or a multitail cell(i.e., a triple-tail cell or quadritail cell). Several kinds of squaring circuits consisting of such transistor-pairs are applied to produce the quadratic bias currents for compensating the nonlinearity of an emitter-and source-coupled pair. Therefore, four circuits using emitter-coupled pairs with adaptive-biasing current and four circuits using source-coupled pairs with adaptive-biasing current are proposed and analyzed in depth. Furthermore, a circuit configuration for low voltage operation is also introduced and verified with bipolar transistor-arrays on a breadboard.

In this study, we investigate the synchronization phenomena of coupled Wien bridge oscillators. The oscillator is characterized by a voltage controlled resistor with saturation. We use linear resistance to couple the oscillators. Two different kinds of coupling techniques, called current and voltage connections are proposed and they show completely opposite mode of synchronized oscillations. The dynamics of the two circuits are also derived to study the amplitude and phase dynamics of the synchronized state. The current connection has a simple resistive effect but stable phase mode is opposite to that of the voltage connection. The voltage connection has the coupling effect which is a combination of resistive and reactive couplings. Coupled three oscillators with current and voltage connection are also studied and stable tri-phase and in-phase synchronizations are observed, respectively. Averaging method is used to investigate the stability of synchronized mode of oscillations. Experimental results are also stated which agree well with the theory.

First, the necessity of examining the numerical calculation of the Bessel function J_ν(x) of complex order ν is explained. Second, the possibility of the numerical calculation of J_ν(x) of arbitrary complex order ν by the use of the recurrence formula is ascertained. The rounding error of J_ν(x) calculated by this method is investigated next by means of theory and numerical experiments when the upper limit of recurrence is sufficiently large. As a result, it was known that there is the possibility that the rounding error grows considerably when ν is complex. Counterplans against the growth of the rounding error will be described.

A problem of obtaining an optimal file transfer on a file transmission net N is to consider how to distribute, with a minimum total cost, copies of a file with some information from a vertex of N to all vertices of N by the respective vertices' copy demand numbers (i.i., needed numbers of copies). The maximum number of copies of file which can be made at a vertex is called the copying number of the vertex. In this paper, we consider as N an arborescence-net with constraints on copying numbers, and give a necessary and sufficient condition for a file transfer to be optimal on N, and furthermore propose an O(n²) algorithm for obtaining an optimal file transfer on N, where n is the number of vertices of N.

Switched-capacitor chaotic neurons fabricated in a full-custom integrated circuit are used to investigate the behavior of 2- and 3-neuron chaotic neural networks. Various sets of parameters are used to visualize the dynamical responses of the networks. Hysteresis of the network is also demonstrated. Lyapunov exponents are approximated from the measured data to characterize the state of each neuron. The effect of the finite length of data and the rounding effect of data acquisition system to the computation of Lyapunov exponents are briefly discussed.

In the actual sound environmental systems, it seems to be essentially difficult to exactly evaluate a whole probability distribution form of its response fluctuation, owing to various types of natural, social and human factors. We have reported a unified probability density expression in the standard expansion form of Hermite type orthonormal series taking a well-known Gaussian probability density function (abbr. p.d.f.) as the basis for generally evaluating non-Gaussian, non-linear correlation and/or non-stationary properties of the fluctuation phenomenon. However, in the real sound environment, there still remain many actual problems on the necessity of improving the above standard type probability expression for practical use. First, a central point in this paper is focused on how to find a new probabilistic theory of practically evaluating the variety and complexity of the actual random fluctuations, especially through newly introducing an equvivalence transformation toward the standard type probability expression mentioned above in the expansion form of Hermite type orthonormal series. Then, the effectiveness of the proposed theory has been confirmed experimentally too by applying it to the actual problems on the response probability evaluation of various sound insulation systems in an acoustic room.

In this letter we propose a stabilizing method of phase control for resistively coupled oscillator networks. To demonstrate the effect of the control, we consider the coupled oscillator system containing only voltage type of connections. A state feedback technique to resistor sub-network is used to control the phase of synchronized oscillation. The technique is applied to two and three coupled oscillator cases. Finally we present experimental results, which agree well with the theory.