The connection admission control is one of preventive traffic control in ATM networks. The one objective of connection admission control is to keep the network load moderate so as to achieve a performance objective associated with quality of services (QOS). Because the cell loss rate is more sensitive to offered load than the average queuing delay in ATM networks, QOS requirement associated with cell loss rate is considered. The connection admission control acts as one of the major roles in traffic control. The job of connection admission control is to make an acceptance decision for connection set-up request to control the network load. This paper proposed and evaluated a connection admission control method. The proposed method is suitable for real time operation even in large diversity of connection types, because the amount of calculation for connection admission control is reduced remarkably compared to conventional algorithms. Moreover, the amount of calculation for the algorithm does not increase even when the number of connection types increases. The proposed method uses probability function for the number of cells transferred from multiplexed connections and uses recursive equations in estimating cell loss rate.

Checkpointing is one of the most powerful tools to operate a computer system with high reliability. We should execute the optimal checkpointing in some sense. This note shows the optimal checkpoint sequence minimizing the expected loss, Numerical examples are shown for illustration.

Kanji Laboratory is a kanji learning ICAI system. In this paper, we describe the development of Kanji Laboratory, which is designed for foreigners who are learning Japanese kanji. We have developed Kanji Laboratory under the guidelines of environmental ICAI systems, based on a kanji learning method focusing on kanji radicals. Kanji Laboratory consists of a knowledge base, a learning environment and an advisor module. The knowledge base can well-handle the knowledge of Joyo Kanji (1,945 characters). Each one is related with its radicals via their inherited attributes. In addition, this knowledge base system can search kanji knowledge quickly. The learning environment has the following features: (1) Students can construct a kanji by combining radicals and disassemble the kanji into radicals and strokes. (2) Students can use electronic tools, such as a kanji dictionary, which support kanji learning. In this way, students can learn kanji and the relations with its radicals effectively. With regard to the advisor, although it occurs that students fall in plateaus of learning in environmental CAI, the advisor module is designed to give well-timed advice to students, avoiding those plateaus, based on the observation of their learning actions.

Experimental evidence of a two-step enhancement in electromigration lifetime is presented through pulsed testing that extends over a wide frequency range from 7 mHz to 50 MHz. It is also found, through an accompanying failure analysis, that the failure mechanism is not affected by current pulsing. Test samples were the lowew metal lines and the through-holes in double-level interconnects. The same results were obtained for both samples. The testing temperature of the test conductor was determined considering the Joule heating to eliminate errors in lifetime estimation due to temperature errors. A two-step enhancement in lifetime is extracted by normalizing the pulsed electromigration lifetime by the continuous one. The first step occurs in the frequency range from 0.1 to 10 kHz where the lifetime increases with (duty ratio)-2 and the second step occurs above 100 kHz with (duty ratio)-3. The transition frequency in the first-step enhancement shifts to the higher frequency region with a decrease in stress temperature or an increase in current density, whereas the transition frequency in the second step is not affected by these stress conditions. The lifetime enhancement is analyzed in relation to the relaxation process during the current pulsing. According to the two-step behavior, two distinct relaxation times are assumed as opposed to the single relaxation time in other proposed models. The results of the analysis agree with the experimental results for the dependence on the frequency and duty ratio of pulses. The two experimentally derived relaxation times are about 5 s and 1 µs.

In this paper we investigate the AM languages that seem to be located outside NP co-NP. We give two natural examples of such AM languages, GIP and GH, which stand for Graph Isomorphism Pattern and Graph Heterogeneity, respectively. We show that the GIP is in ΔP2 AM co-AM but is unlikely to be in NP co-NP, and that GH is in ΔP2 AM but is unlikely to be in NP co-AM. We also show that GIP is in SZK. We then discuss some structural properties related to those languages: Any language that is polynomial time truth-table reducible to GIP is in AM co-AM; GIP is in co-SZK if SZK co-SZK is closed under conjunctive polynomial time bounded-truth-table reducibility; Both GIP and GH are in DP. Here DP is the class of languages that can be expressed in the form X Y, where X NP and Y co-NP.

In this paper, we study the knowledge tightness of zero-knowledge proofs. To this end, we present a new measure for the knowledge tightness of zero-knowledge proofs and show that if a language L has a bounded round zero-knowledge proof with knowledge tightness t(|x|) 2 - |x|-c for some c 0, then L BPP and that any language L AM has a bounded round zero-knowledge proof with knowledge tightness t(|x|) 2-2-O(|x|) under the assumption that collision intractable hash functions exist. This implies that in the case of a bounded round zero-knowledge proof for a language L BPP, the optimal knowledge tightness is "2" unless AM = BPP. In addition, we show that any language L IP has an unbounded round zero-knowledge proof with knowledge tightness t(|x|) 1.5 under the assumption that nonuniformly secure probabilistic encryptions exist.

This paper proposes an optimal free-sensors allocation problem (OFSAP) in safety monitoring systems. OFSAP is the problem of deciding the optimal allocation of several sensors, which we call free sensors, to plural objects. The solution of OFSAP gives the optimal allocation which minimizes expected losses caused by failed dangerous (FD)-failures and failed safe (FS)-failures; a FD-failure is to fail to generate an alarm for unsafe object and a FS-failure is to generate an alarm for safe object. We show an unexpected result that a safer object should be monitored by more sensors under certain conditions.

In a probabilistic graph (network), source-to-all-terminal (SAT) reliability may be defined as the probability that there exists at least one path consisting only of successful arcs from source vertex s to every other vertex. In this paper, we define an optimal SAT reliability formula to be the one with minimal number of literals or operators. At first, this paper describes an arc-reductions (open- or short-circuiting) method for obtaining a factored formula of directed graph. Next, we discuss a simple strategy to get an optimal formula being a product of the reliability formulas of vertex-section graphs, each of which contains a distinct strongly connected component of the given graph. This method reduces the computing cost and data processing effort required tu generate the optimal factored formula, which contains no identical product terms.

In this paper, we investigate the knowledge complexity of interactive proof systems and show that (1) under the blackbox simulation, if a language L has a bounded move public coin interactive proof system with polynomially bounded knowledge complexity in the hint sense, then the language L itself has a one move interactive proof system; and (2) under the blackbox simulation, if a language L has a three move private coin interactive proof system with polynomially bounded knowledge complexity in the hint sense, then the language L itself has a one move interactive proof system. These results imply that as long as the blackbox simulation is concerned, any language L AM＼MA is not allowed to have a bounded move public coin (or three move private coin) interactive proof system with polynomially bounded knowledge complexity in the hint sense unless AM = AM. In addition, we present a definite distinction between knowledge complexity in the hint sense and in the strict oracle sense, i.e., any language in AM (resp. IP) has a two (resp. unbounded) move public coin interactive proof system with polynomially bounded knowledge complexity in the strict oracle sense.

In this paper an identity-based non-interactive key sharing scheme (IDNIKS) is proposed in order to realize the original concept of identity-based cryptosystem, of which secure realization scheme has not been proposed. First the necessary conditions for secure realization of IDNIKS are considered from two different poinrts of view: (i) the possibility to share a common-key non-interactively and (ii) the security for entity's conspiracy. Then a new non-interactive key sharing scheme is proposed, of which security depends on the difficulty of factoring. The most important contribution is to have succeeded in obtaining any entity's secret information as an exponent of the obtainer's identity information. The security of IDNIKS for entity's conspiracy is also considered in details.

In this paper, we present an electronic voting scheme with a single voting center using an anonymous channel. The proposed scheme is a 3-move protocol between each voter and the center, with one extra move if one wants to make objection to the tally. This objection can be broadcasted widely since it will not disclose the vote itself to the other parties besides the center. The main idea in the proposal is that each voter sends anonymously a public key signed by the center and an encrypted vote decryptable using this key. Since even the center cannot modify a received ballot to a different vote using the same public key, the key can be used as an evidence in making open objection to the tally.

An efficient algorithm is presented for finding all solutions of piecewise-linear resistive circuits. In this algorithm, a simple sign test is performed to eliminate many linear regions that do not contain a solution. This makes the number of simultaneous linear equations to be solved much smaller. This test, in its original form, is applied to each linear region; but this is time-consuming because the number of linear regions is generally very large. In this paper, it is shown that the sign test can be applied to super-regions consisting of adjacent linear regions. Therefore, many linear regions are discarded at the same time, and the computational efficiency of the algorithm is substantially improved. The branch-and-bound method is used in applying the sign test to super-regions. Some numerical examples are given, and it is shown that all solutions are computed very rapidly. The proposed algorithm is simple, efficient, and can be easily programmed.

The structural necessary and sufficient condition for "the transition-liveness means the place-liveness and vice-versa" of a subclass NII of general Petri nets is given as "the place and transition live Petri net, or PTL net, ÑII". Furthermore, "the one-token-condition Petri net, or OTC net, II" which means that every MSDL (minimal structural deadlock) is "transition and place live" under at least one initial token, i.e., II is "transition and place live" under the above initial marking. These subclasses NII, ÑII( NII), and II(ÑII) are almost the general Petri nets except at least one MSTR(minimal structural trap) and at least one pair of "a virtual MSTR or a virtual STR" and "a virtual MSDL" of an MBTR (minimal behavioral trap) in connection with making an MSDL transition-live.

Server aided secret computation (SASC) protocol also called the verifiable implicit asking protocol, is a protocol such that a powerful untrusted auxiliary device (server) can help a smart card (client) for computing a secret function efficiently. In this paper, we extend the concept of addition sequence to the secure addition sequence and develop an efficient algorithm to construct such sequence. By incorporating the secure addition sequence into the SASC protocol the performance of SASC protocol can be further enhanced.

It is often desired to change the cutoff frequencies of digital filters in some applications like digital electronic instruments. This paper proposes a design of variable lowpass digital filters with wider ranges of cutoff frequencies than conventional designs. Wave digital filters are used for the prototypes of variable filters. The proposed design is based on the frequency scaling in the s-domain, while the conventional ones are based on the z-domain lowpass-to-lowpass transformations. The first-order approximation by the Taylor series expansion is used to make multiplier coefficients in a wave digital filters obtained from a frequency-scaled LC filter become linear functions of the scaling parameter, which is similar to the conventional design. Furthermore this paper discusses the reduction of the approximation error. The curvature is introduced as the figure of the quality of the first-order approximation. The use of the second-order approximation to large-curvature multiplier coefficients instead of the first-order one is proposed.

It is important for LSI system designers to estimate computational errors when designing LSI's for numeric computations. Both for the prediction of the errors at an early stage of designing and for the choice of a proper hardware configuration to achieve a target performance, it is desirable that the errors can be estimated in terms of a minimum of parameters. This paper presents a theoretical error analysis of multiply-accumulation implemented by distributed arithmetic(DA) and proposes a new method for estimating the mean-squared error. DA is a method of implementing the multiply-accumulation that is defined as an inner product of an input vector and a fixed coefficient vector. Using a ROM which stores partial products. DA calculates the output by accumulating the partial products bitserially. As DA uses no parallel multipliers, it needs a smaller chip area than methods using parallel multipliers. Thus DA is effectively utilitzed for the LSI implementation of a digital signal processing system which requires the multiply-accumulation. It has been known that, if the input data are uniformly distributed, the mean-squared error of the multiply-accumulation implemented by DA is a function of only the word lengths of the input, the output, and the ROM. The proposed method for the error estimation can calculate the mean-squared error by using the same parameters even when the input data are not uniformly distributed. The basic idea of the method is to regard the input data as a combination of uniformly distributed partial data with a different word length. Then the mean-squared error can be predicted as a weighted sum of the contribution of each partial data, where the weight is the ratio of the partial data to the total input data. Finally, the method is applied to a two-dimensional inverse discrete cosine transform (IDCT) and the practicability of the method is confirmed by computer simulations of the IDCT implemented by DA.

This paper is concerned with the continuous relation between models of the plant and the predicted performances of the system designed based on the models. To state the problem more precisely, let P be the transfer matrix of a plant model, and let A be the transfer matrix of interest of the designed system, which is regarded as a performance measure for evaluating the designed responses. A depends upon P and is written as A=A(P). From the practical point of view, it is necessary that the function A(P) should be continuous with respect to P. In this paper we consider the linear quadratic optimal servosystem with integrators (LQI) scheme as the design methodology, and prove that A(P) depends continuously on the plant transfer matrix P if the topology of the family of plants models is the graph topology. A numerical example is given for illustrating the result.

This letter deals with the reliability function in the case of periodic preventive replacement of items in order to increase MTBF, that is, two replacement policies; strictly periodic replacement (SPR) and randomly periodic replacement (RPR). We stress on simple introduction of the reliability theory under preventive replacement policies using the Laplace transform and obtain the theoretical results of SPR and RPR. Then these results are applied to the Weibull distribution and finally in order to show useful information of preventive replacement, the numerical results of SPR are provided.

In 1963, the authors began to develop a tuning circuit (hereafter referred to as the 'circuit') consisting of an inductor, fixed capacitors and a variable capacitor. The circuit required very high accuracy and stability, and the aging influence on resonant frequency needed to be Δf/f0 0.12% for 20 years. When we started, there was no methodology available for designing such a long-term stable circuit, so we reinvestigated our previous studies concerning aging characteristics and formed a design concept. We designed the circuit by bearing in mind that an inductor was subject to natural and stress demagnetization (as indicated by disaccommodation), and assumed that a capacitor changed its characteristics linearly over a logarithmic scale of time. (This assumption was based on short-term test results derived from previous studies.) We measured the aging characteristics of the circuits at room temperature for 20 years, from 1966. The measurement results from the 20-year study revealed that the aging characteristics predicted by the design concept were reasonably accurate.

This paper describes mixed gas systems of SO2 and NO2 which are the essential corrosive gases in an ordinary atmospheric environment of electronic parts. It describes the corrosion product compositions and the behavior of copper in mixed and separate gases. Results of our tests show the following: (1) The weight of corrosion products with the SO2-NO2 mixed gas approximate the sum of those with the individual gases, however, the corrosion products of SO2 are affected by NO2. (2) Tests of the SO2-NO2 mixed gas closely simulates tests of electronic parts in the ordinary atmospheric environment.