We consider single machine problems involving both specific and generalized due dates simultaneously. We show that a polynomial time algorithm exists for the problem of minimizing max {Lmax, LHmax}, where Lmax and LHmax are the maximum lateness induced by specific and generalized due dates, respectively. We also show that a simple efficient algorithm exists for the problem of minimizing the maximum lateness induced by due dates which are natural generalization of both specific and generalized due dates. In addition to the algorithmic results above, we show that the problems of minimizing max {LHmax, -Lmin} and max{Lmax, -LHmin} are NP-hard in the strong sense, where Lmin and LHmin are the minimum lateness induced by specific and generalized due dates, respectively.

The present paper describes a novel approach to interconnecting and assembling components of MEMS at room temperature. The main drawback of the conventional bonding methods is their rather high process temperatures. The new method, which is referred as the surface activated bonding (SAB), utilizes the phenomena of the adhesion between two atomically clean solid surfaces to enable the bonding at lower temperature or even at room temperature. In the bonding procedure, the surfaces to be bonded are merely brought into contact after sputter-cleaning by Ar fast atom in ultrahigh vacuum conditions. TEM observations of the bonded interfaces show that a direct bonding in atomic scale is achieved in the interface between the micro-components. Based on the concept of this new bonding technology, a micro-assembly system was developed. The micro-assembly system is operated by means of a virtual manipulation system in which 3D model of the micro-components are manipulated virtually in a computer graphics constructed in the world wide web (WWW) scheme. The micro-assembly system will provide a new design tool of three dimensional MEMS by combining the possibility of the flexible assembly and the intuitive operations.

Micromechanisms and actuators which are 10-100 micrometers in size are studied by research groups in universities, national research institutes, and private industries in Japan. Some of them belong to a "Micromachine Technology" project lead by MITI (Ministry of International Trade and Industries). Microfabrication technologies based on both IC-compatible processes and mechanical machining are under development. Application-oriented devices in automobile, communication and information industries are also investigated. The research goal is to build a smart micro system through the integration of moving mechanisms, sensors and electronics on a chip; this is the fusion of mechanics and electronics in the microscopic world. This paper reviews recent activities in MEMS research in Japan.

Photovoltaic devices capable of generating more than 200 volts with an area of 1 cm2 have been developed for directly driving microactuators such as piezoelectric or electrostatic actuators. The micro-devices interconnect 285 micro cells (unit cell size: about 0.5 mm 2.0 mm) in series, and have an open circuit voltage (Voc) of 207 volts, a short circuit current (Isc) of 36.6 µA, a maximum output power (Pmax) of 4.65 mW and a fill factor (F.F.) of 0.615 under AM (Air Mass) 1.5 and 100 mW/cm2 illumination. This voltage is the highest in the world for the area of 1 cm2. The series connection is precisely processed by a focused laser beam, thereby significantly reducing the area needed for device connections. It has been confirmed that a piezoelectric polymer can be directly driven by the electrical output in evaluating the potential of the devices to be used as a microactuator's power source.

The growing availability of commercial foundry processes allows easy implementation of micro-opto-electro-mechanical systems (MOEMS) for a variety of applications. Such applications go beyond single devices to include whole optical systems on a chip, consisting of mirrors, gratings, Fresnel lenses and shutters, for example. Hinged and rotating structures, combined with powerful and compact thermal actuators, provide the means for positioning and operating these optical components. This paper presents examples of such systems built in a commercial polycrystalline silicon surface-micromachining process, the ARPA-sponsored Multi-User MEMS ProcesS (MUMPS). Examples range from optical sub-components to large mirror arrays, communication components, and micro-interferometers. Using the examples discussed in this paper, a designer can take advantage of commercially available surface-micromachining processes to design and develop MOEMS without the need for extensive in-house micromachining capabilities.

This paper describes the fabrication of micro-pipes and their applications to splicing parts and optical switches using single-mode fibers. Micro-pipes having almost the same inner diameter of bare fiber (125 µm) and lengths of around 5 mm are successfully mass-produced by using micromachining technology. We fabricate various kinds of metal pipes such as Au, Cu, Ni, and an FeNi alloy by selecting the appropriate electro-plating bath. We use an Au micro-pipe having a small slitted portion running along its axis (slitted micro-pipe) to splice single-mode fibers. We also use an FeNi alloy micro-pipe to construct a single-mode fiber switch. These new single-mode fiber devices employing micro-pipes show excellent optical and mechanical characteristics. Splicing losses are in the range of 0.2-0.4 dB. The developed 1 2 latching type single-mode fiber switches exhibit a low insertion loss of 0.35 dB, a minimum switching speed of 2 ms with a driving power of 9 mW, and stable operation for more than 108 switchings without damage. A practical application of the developed switch for testing optical devices is also demonstrated.

A new silicon capacitive pressure sensor with center clamped diaphragm is presented. The sensor has a silicon-glass structure and is fabricated by batch-fabrication processes. Since deformed diaphragm has a doughnut-shape, parallel-like displacement is realized and therefore better linearity of 0.7% which is half of the conventional flat diaphragm sensor is obtained. It is clarified both analytically and experimentally that the capacitive pressure sensor with center clamped diaphragm is advantageous in terms of linearity.

We describe the design, fabrication, and characteristics of FDM/WDM coupler deposited by TEOS-O3 based APCVD method on silicon substrates. Due to drastically reduced birefringence by APCVD process, completely polarization independent narrow band (100 GHz) Mach-Zehnder type FDM coupler was obtained. We also fabricated 1.3/1.55 µm directional coupler type WDM coupler with very low insertion loss.

The response time of adders is mainly determined by the carry propagation delay. This letter deals with a scheme which combines the address addition and decoding together. Although addition is involved in the process, we show that it can be computed without carry propagation. Memory latency is one of the most performance limiting factors. The authors present a new decoder logic named fused add-decoder (FADEC), which performs address addition and decoding in a single process. FADEC can reduce memory latency by eliminating separate address addition cycle.

This paper proposes a new approach for distributing millimeter wave signals from a central location to micro-base-stations using optical fiber links. The links utilize two Mach-Zehnder external optical modulators (EOMs) to perform all optical down-conversion, eliminating the need for a local oscillator or laser diode in the micro-base-station. A simple model of the EOMs is developed to illustrate the principle of dual-EOM mixing. The characteristics of conversion loss and intermodulation are examined for two cases: where the EOMs are operated in the linear mode and where the local oscillator's EOM is biased as a frequency doubling modulator. Additionally, we examined the use of an optical amplifier to reduce conversion loss for these two cases. The measured conversion loss of the link was 82 dB, and we estimated this could be reduced to about 48 dB by employing an optical amplifier and a more efficient EOM for RF reception.

Roundoff error due to iterative computation with finite wordlength degrades the quality of decoded images in fractal image coding that employs a deterministic iterated function system. This paper presents a state-space approach to roundoff error analysis of fractal image coding for grey-scale images. The output noise variance matrix and the noise matrix are derived for the measures of error and the output noise variance is newly defined as the pixel mean of diagonal elements of the output noise matrix. A quantitative comparison of experimental roundoff error with analytical result is made for the output noise variance. The result shows that our analysis method is valid for the fractal image coding. Our analysis method is useful to design a real-time and low-cost decoding hardware with finite wordlength for fractal image coding.

In a conventional client-server system using the satellite communications, the responsibility of the system to the client user is considerably degraded by the long transmission time between the satellite and the ground terminal as well as the relatively low data transmission rate in comparison with the ground transmission line as the Ethernet. In this paper, a new client-server control, VEEC, is proposed to solve the problem. As a result of the experimental performance studies, it is clarified that the responsibility in the client is remarkably improved when the pre-fetching mechanism of VEEC works efficiently.

A requirement specification acquisition method combined with hypothesis-based reasoning and model reasoning is proposed for obtaining service specifications from the ambiguous and/or incomplete requirement specifications of communications services. Errors at an early stage of software development cost more to debug than those at a later stage. Specification acquisition is the most upstream development process. Nevertheless, the system support for specification acquisition is delayed compared with other development phases.' Users do not always have precise requirements. It is therefore inevitable that user requirements contain ambiguities, insufficiencies and even contradictions. Considering this, it is indispensable to support a specification completion method that derives service specifications from such problem requirements. This paper proposes a combined method to obtain consistent and complete specifications from such problem requirements. Communications service specifications can be described by specifying terminal behaviors which can be recognized from outside the communications system(s). Such specifications are described by a rule-based language. Requirement specifications usually have components that are ambiguous, incomplete, or even contradictory. They appear as rule description and/or missing rules. From such requirements, service specifications are obtained by using hypothesis-based reasoning on input requirements and existing service specifications. When existing specifications cannot be used to obtain complementary specifications, a communications service model is used to propose new rules. The proposed methods are implemented as a part of a communications software development system. The system enables non-experts in communications systems to define their own service specifications.

In [2] Ibarra introduced a restricted version of one-way multihead pushdown automaton (PDA), called a simple one-way multihead PDA, and showed that such machines recognize only languages with semilinear property. The main result of this paper is that for each k 1, simple (sensing) one-way (k + 1)-head PDA's are more powerful than simple (sensing) one-way k-head PDA's. This paper also investigates closure properties for simple (sensing) one-way multihead PDA's

An embedded cache memory for low power RISC microprocessors is described. An automatic-power-save architecture (APSA) enables the cache memory to operate with high speed at high frequencies, and with low power dissipation at low frequencies. A pulsed word technique (PWT) and an isolated bit line technique (IBLT) reduce the power dissipation of the cache memory effectively. Using these three techniques, the power dissipation of the cache memory is reduced to almost 60% of the conventional cache memory at 60 MHz and to 20% at a clock frequency of 10 MHz. An 8 KByte test chip using 0.5 µm CMOS technology was fabricated, and it achieves 80 MHz operation at a supply voltage of 3.1 V, and 8 mW operation at a supply voltage of 2.5 V at 10 MHz.

A direct-mapped cache takes less time for accessing data than a set-associative cache because the time needed for selecting a cache line among the set is not necessary. The hit ratio of a direct-mapped cache, however, is lower due to the conflict misses caused by mapping multiple addresses to the same cache line. Addressing cache memory by virtual addresses reduces the cache access time by eliminating the time needed for address translation. The synonym problem in virtual cache necessitates an additional field in the cache tag to denote the process to which cache line belongs. In this paper, we propose a new virtual cache architecture whose average access time is almost the same as the direct-mapped caches while the hit ratio is the same as the set-associative cashes. A victim for cache replacement is selected from those that belong to a process which is most remote from being scheduled. The entire cache memory is divided into n banks, and each process is assigned to a bank. Then, each process runs on the assigned bank, and the cache behaves like a direct-mapped cache. Trace-driven simulations confirm that the new scheme removes almost as many conflict misses as does the set-associative cache, while cache access time is similar to a direct-mapped cache.

Let SeH{0}(k) [NSeH{0}(k)] denote the class of languages over a one-letter alphabet accepted by two-way sensing deterministic [nondeterministic] k-head finite automata. This paper shows that (i) SeH{0}(2)SeH{0}(3), and (ii) NSeH{0}(2) NSeH{0}(3). This gives an affirmative answer to an open problem in Ref. [3].

For reversal complexity on an off-line Turing machine, which is a Turing machine with a read-only two-way input tape except work-tapes, we can consider two kinds of definition; the first one is a definition in which the number of reversals over the input tape is not counted, and the second one is a definition in which it is counted. Unlike time and space complexities, whether or not there is any difference between these two definitions does not seem to be trivial. In this paper, we will show the following results: (1) let S(n) be any function, and R(n) be an (R(n), S(n)) reversal-space constructible function. Then, DRESPk(R(n), S(n)) IDRESPk+2(R(n) + log(nS(n)), n2R(n)S(n)), (2) let R(n) and S(n) be any functions. Then, NRESPk(R(n), S(n)) INRESPk+1(R(n), n2S(n)), and ARESPk(R(n), S(n)) = IARESPk(R(n), S(n)), where DRESP denotes a deterministic reversal- and space-bounded class under the definition disregarding reversals over the input tape, and IDRESP denotes a deterministic reversal- and space-bounded class under the definition counting it. The suffix k denotes the number of work-tapes. The classes NRESP, INRESP, ARESP and IARESP are also defined similarly for NTMs and ATMs.

Petri net is a graphical and mathematical modeling tool for discrete event systems. This paper treats analysis problems for Petri nets under the earliest firing rule. Under this firing rule, transitions must fire as soon as they are enabled. Marked Petri nets under the earliest firing rule are called earliest firing systems, for short. First, some relations in analysis problems between the earliest and the normal firing systems are discussed. These problems include deadlock freedom, boundedness, persistency and liveness. Then, relations among three types of reachability are considered from the viewpoint of the earliest firing rule. Since earliest firing systems can simulate register machines, they have equivalent modeling powers to Turing machines. It suggests, however, that most of the analysis problems of earliest firing systems with general net structures are undecidable. In this paper, net structures are restricted to a subclass called dissynchronous choice (DC) nets. It is shown that the reachability problem from an initial marking to dead markings (markings where no transition can fire) in earliest firing DC systems is equivalent to the usual reachability problem of the same systems under the normal firing rule. Then, the result is applied to reachability problems of controlled DC systems in which some transitions in the net have external control input places. It is shown that for systems where every transition in the net has an external control input place, one type of reachability problem is decidable. Lastly, the liveness problem of earliest firing DC systems is considered and it is shown that this problem is equivalent to that of the underlying DC system under the normal firing rule. It is also shown that this liveness problem is decidable.

In this paper we present an efficient method to solve reachability problems for Petri nets based on genetic algorithms and a kind of random search which is called postpone search. Genetic algorithm is one of algorithms developed for solving several problems of optimization. We apply GAs and postpone search to approximately solving reachability problems. This approach can not determine exact solutions, however, from applicability points of view, does not directly face state space explosion problems and can extend class of Petri nets to deal with very large state space in reasonable time. First we describe how to represent reachability problems on each of GAs and postpone search. We suppose the existence of a nonnegative parickh vector which satisfies the necessary reachability condition. Possible firing sequences of transitions induced by the parickh vector is encoded on GAs. We also define fitness function to solve reachability problems. Reachability problems can be interpreted as an optimization ones on GAs. Next we introduce random reachability problems which are capable of handling state space and the number of firing sequences which enable to reach a target marking from an initial marking. State space and the number of firing sequences are considered as factors which effect on the hardness of reachability problems to solve with stochastic methods. Furthermore, by using those random reachability problems and well known dining philosophers problems as benchmark problems, we compare GAs' performance with the performance of postpone search. Finally we present empirical results that GAa is more useful method than postpone search for solving more harder reachability problems from the both points of view; reliability and efficiency.