In order to reduce state explosion problem, techniques such as symbolic state space traversal and partial order reduction have been proposed. Combining these two techniques, however, seems difficult, and only a few research projects related to this topic have been reported. In this paper, we propose handling single place zero reachability problem of Petri nets by using both partial order reduction and symbolic state space traversal based on ZBDDs. We also show experimental results of several examples.

Ultra-low-power-consumption and high-speed DCFL circuits have been fabricated by using 0.2-µm Y-shaped gate E/D-heterojunction-FETs (HJFETs) with a high-aspect-ratio gate-structure, which has an advantage of reducing the gate-fringing capacitance (Cf) to about a half of that of a conventional low-aspect-ratio one. A fabricated 51-stage ring oscillator with the 0.2-µm Y-shaped gate n-AlGaAs/i-InGaAs E/D-HJFETs shows the lowest power-delay product of 0.21 fJ with an unloaded propagation delay of 34.9 ps at a supply voltage (VDD) of 0.4 V. We also analyze the DCFL switching characteristics by taking into account the intrinsic gate-to-source capacitance (Cgsint) and the Cf. The analysis results for the power-delay products agree well with our experimental results. Our analysis also indicates the DCFL circuit with the high-aspect-ratio Y-shaped gate E/D-HJFETs can reduce the power-delay products by 35% or more below 0.25-µm gate-length as compared to conventional ones with the low-aspect-ratio Y-shaped gate HJFETs. These results clarify that the Cf-reduction of the Y-shaped gate HJFETs is more effective in improving the power-delay products than reducing the gate-length.

We experimentally demonstrate the ultrafast and high-repetition capabilities of a polarization-discriminating symmetric Mach-Zehnder (PD-SMZ) all-optical switch. This switch, as well as an original symmetric Mach-Zehnder (SMZ) all-optical switch, is based on a highly efficient but slowly relaxing band-filling effect that is resonantly excited in a passive InGaAsP bulk waveguide. By using a mechanism that cancels out the effect of the slow relaxation, ultrafast switching is attained. We achieve a switching time of 200 fs and demultiplexing of 1.5 Tbps, showing the applicability of the SMZ or PD-SMZ all-optical switches to optical demultiplexing of well over 1 Tbps for the first time. High-repetition capability, which is another important issue apart from the switching speed, is also verified by using control pulses at a repetition rate of 10.5 GHz. We also discuss the use of nonlinearity in a semiconductor optical amplifier to further reduce the control-pulse energy.

We experimentally demonstrate the ultrafast and high-repetition capabilities of a polarization-discriminating symmetric Mach-Zehnder (PD-SMZ) all-optical switch. This switch, as well as an original symmetric Mach-Zehnder (SMZ) all-optical switch, is based on a highly efficient but slowly relaxing band-filling effect that is resonantly excited in a passive InGaAsP bulk waveguide. By using a mechanism that cancels out the effect of the slow relaxation, ultrafast switching is attained. We achieve a switching time of 200 fs and demultiplexing of 1.5 Tbps, showing the applicability of the SMZ or PD-SMZ all-optical switches to optical demultiplexing of well over 1 Tbps for the first time. High-repetition capability, which is another important issue apart from the switching speed, is also verified by using control pulses at a repetition rate of 10.5 GHz. We also discuss the use of nonlinearity in a semiconductor optical amplifier to further reduce the control-pulse energy.

Design and evaluation of a high-performance switch architecture for free-space photonic switching systems is described. The switch is constructed of 22 switching elements and employs special multistage interconnection patterns. The connection setup algorithm and the control procedure at the switching elements are based on a "rerouting algorithm." Performance analysis shows that the blocking probability of the switch is easily controlled by increasing the number of switching stages. Example implementations of this switch are shown in which birefringent plates, polarization controllers, etc. are used.

Design and evaluation of a high-performance switch architecture for free-space photonic switching systems is described. The switch is constructed of 22 switching elements and employs special multistage interconnection patterns. The connection setup algorithm and the control procedure at the switching elements are based on a "rerouting algorithm."" Performance analysis shows that the blocking probability of the switch is easily controlled by increasing the number of switching stages. Example implementations of this switch are shown in which birefringent plates, polarization controllers, etc. are used.

This paper proposes a bit-commitment scheme, BC(), and an efficient statistical zero-knowledge (in short, SZK) protocol in which, for any given multi-variable polynomial, f(X1,,Xt), and any given modulus, n, a prover, P, gives (I1,,It) to a verifier,ν, and can convince ν that P knows (x1,,xt) which satisfies f(x1,,xt) 0 (mod n) and Ii = BC(xi), (i = 1,,t). The proposed protocol is O(|n|) times more efficient than the corresponding previous ones. The (knowledge) soundness of our protocol holds under a computational assumption, the intractability of a modified RSA problem (see Def. 3.2), while the (statistical) zero-knowledgeness of the protocol needs no computational assumption. The protocol can be employed to construct various practical cryptographic protocols, such as fair exchange, untraceable electronic cash and verifiable secret sharing protocols.

The paper investigates several approaches for designing and implementing integration environments. Such an environment is developed for the purpose to allow cooperative interactions between distributed and heterogeneous systems. A possible approach to achieve system integration is to use the warehousing technology which engenders the development of data warehousing environments. These environments are information repositories that are available for queries and analysis. In order to manage efficiently a data warehouse, software agents enhanced with mobility mechanisms are introduced. A software agent is an autonomous entity having the abilities to collaborate with each other and to answer users' needs. Furthermore, to perform their operations software agents can migrate off their hosts and roam the network to gather relevant information. This research is part of the SAMDW project which aims at developing a new generation of data warehouses.

In this paper, we propose a method for querying heterogeneous molecular biology databases. Since molecular biology data are distributed into multiple databases that represent different biological domains, it is highly desirable to integrate data together with the correlations between the domains. However, since the total amount of such databases is very large and the data contained are frequently updated, it is difficult to maintain the integration of the entire contents of the databases. Thus, we propose a method for dynamic integration based on user demand, which is expressed with an OQL-based query language. By restricting search space according to user demand, the cost of integration can be reduced considerably. Multiple databases also exhibit much heterogeneity, such as semantic mismatching between the database schemas. For example, many databases employ their own independent terminology. For this reason, it is usually required that the task for integrating data based on a user demand should be carried out transitively; first search each database for data that satisfy the demand, then repeatedly retrieve other data that match the previously found data across every database. To cope with this issue, we introduce two types of agents; a database agent and a user agent, which reside at each database and at a user, respectively. The integration task is performed by the agents; user agents generate demands for retrieving data based on the previous search results by database agents, and database agents search their databases for data that satisfy the demands received from the user agents. We have developed a prototype system on a network of workstations. The system integrates four databases; GenBank (a DNA nucleotide database), SWISS-PROT, PIR (protein amino-acid sequence databases), and PDB (a protein three-dimensional structure database). Although the sizes of GenBank and PDB are each over one billion bytes, the system achieved good performance in searching such very large heterogeneous databases.

This paper proposes the first provably secure multi-signature schemes under the random oracle model. The security of our schemes can be proven in the sense of concrete security in Ref. [13]. The proposed schemes are efficient if the random oracle is replaced by practical hash functions. The essential techniques in our proof of security are the optimal reduction from breaking the corresponding identification to breaking signatures (ID Reduction Technique), and the hierarchical heavy row lemmas used in the concrete reduction from solving the primitive problem to breaking the identification scheme.

We investigated a radio interferometer for geodetic use that incorporates commercially available fiber-optic links modulated in the radio-frequency range, and a method for compensating for the delay occurring in the links. With this type of radio interferometer, we can perform baseline analysis without the need for estimating the clock difference between observation stations, which causes a relatively large error in the vertical component of the estimated position of the station. Another advantage of the interferometer is utilization of phase delay, which improves the accuracy of delay determination considerably. By analyzing the interferometer's signal-to-noise ratio, we estimated the practicable cable length to be 58.0 km. The results of preliminary experiments with short optical fiber links show that the differences in the cable delays of the fiber-optic links can be compensated for by calibration signals which make a round trip between the analysis station and the observation sites, and that phase delay can be measured successfully.

In 1992 Burmester studied how to adapt the Guillou-Quisquater identification scheme to a proven zero-knowledge proof without significantly increasing the communication complexity and computational overhead. He proposed an almost constant round version of Guillou-Quisquater. Di Crescenzo and Persiano presented a 4-move constant round zero-knowledge interactive proof of membership for the corresponding language. A straightforward adaptation of the ideas of Bellare-Micali-Ostrovsky will also give a constant round protocol. However, these protocols significantly increase the communication and computational complexity of the scheme. In this paper we present constant round variants of the protocols of Guillou-Quisquater and Schnorr with the same (order-wise) communication and computational complexity as the original schemes. Note that in our schemes the probability that a dishonest prover will fool a honest verifier may be exponentially small, while it can only be one over a superpolynomial in Burmester's scheme. Our protocols are perfect zero-knowledge under no cryptographic assumptions.

A novel zero-voltage-switched half-bridge converter is proposed. This converter achieves the zero-voltage switching while maintaining a constant frequency PWM control. Then the power conversion of high efficiency and low noise is realized at a higher switching frequency. In the experiment, a high efficiency of 83% is achieved for a low output voltage of 3.3 V, an output current of 30 A, and an input-voltage range of 200 to 400 V at the switching frequency of 400 kHz.

We have analyzed a very short channel tunneling field effect transistor which uses new heterostructures (CoSi2/Si/CdF2/CaF2) lattice-matched to the Si substrate. In device operation, the drain current from source (CoSi2) to drain (CoSi2) through tunnel barriers (Si) and the channel (CdF2) is controlled by a gate electric field applied to the barrier between the source and the channel through the gate insulator (CaF2). Theoretical analysis shows that this transistor has characteristics similar to those of conventional metal-oxide-semiconductor field effect transistors even with channel lengths as short as 5 nm. In addition, we have estimated the theoretical response time of this transistor and showed the possibility of subpicosecond response.

This paper proposes two types of acceleration parameters for the Durand-Kerner method and its variant, where the values of parameters are determined at each iteration step. Numerical examples are also shown.

A zerotree image-coding scheme is introduced that effectively exploits the inter-scale self-similarities found in the octave decomposition by a wavelet transform. A zerotree is useful for efficiently coding wavelet coefficients; its efficiency was proved by Shapiro's EZW. In the EZW coder, wavelet coefficients are symbolized, then entropy-coded for further compression. In this paper, we analyze the symbols produced by the EZW coder and discuss the entropy for a symbol. We modify the procedure used for symbol-stream generation to produce lower entropy. First, we modify the fixed relation between a parent and children used in the EZW coder to raise the probability that a significant parent has significant children. The modified relation is flexibly modified again based on the observation that a significant coefficient is more likely to have significant coefficients in its neighborhood. The three relations are compared in terms of the number of symbols they produce.

In this paper, we study the optimal allocation of multimedia files in distributed network systems. In these systems, the files are shared by users connected with different servers geographically separated, and each file must be stored in at least one of servers. Users can access any files stored in any servers connected with high-speed communication networks. Copies of the files accessed frequently are to be stored in several servers that have databases. So, it is one of the most important problems how to assign the files to servers in view of costs and delays. Considering these problems in heterogeneous network environments, we present a new system model that covers wide range of multimedia network applications like VOD, CALS, and so on. In these systems, it is obvious that there is trading-off relationship between costs and delays. Our objective is to find the optimal file allocation such that the total cost is minimized subject to the total delay. We introduce a 0-1 integer programming formulation for the optimization problem, and find the optimal file allocation by solving these formulae.

This paper studies a set of lip synchronization mechanisms for heterogeneous network environments. The set consists of four schemes, types 0 through 3, which are classified into the single-stream approach and the multi-stream approach. Types 0 and 1 belong to the single-stream approach, which interleaves voice and video to form a single transport stream for transmission. On the other hand, types 2 and 3, both of which are the multi-stream approach, set up separate transport streams for the individual media streams. Types 0 and 2 do not exert synchronization control at the destination, while types 1 and 3 do. We first discuss the features of each type in terms of networks intended for use, required synchronization quality of each medium, physical locations of media sources and implementation complexity. Then, a synchronization algorithm, which is referred to as the virtual-time rendering (VTR) algorithm, is specified for stored media; MPEG video and voice are considered in this paper. We implemented the four types on an ATM LAN and on an interconnected ATM-wireless LAN under the TCP protocol. The mean square error of synchronization, total pause time, throughput and total output time were measured in each of the two networks. We compare the measured performance among the four types to find out which one is the most suitable for a given condition of the underlying communication network and traffic.

High- and low-reflection Bragg gratings with a flat-top spectral response free from ripples are proposed. Add/drop filters are created based on gratings photoinduced on planar waveguides by using the new design schemes. The measured spectral responses for the high and low reflection gratings are in good agreement with the calculated ones, and show the flat-top spectral responses.

An equivalent circuit for designing a coherent power combiner using a quasi-optical resonator has been developed. In the resonator, large numbers of devices (HEMT, HBT, etc. ) are arrayed two dimensionally and mounted on a surface of a metal grooved-mirror. A newly developed equivalent circuit for the resonator has been constructed using a transmission-line model. Experiments performed at Ku-band have shown that oscillation frequencies in a 33 HEMT array oscillator can be predicted with errors of less than 1% by using this equivalent circuit.