Suppose that there are terminals on two concentric circles Cin and Cout, with Cin inside of Cout. A set of two-terminal nets is given and the routing area is the annular region between the two circles. In this paper, we present an O(n2) time algorithm for testing whether the given net set is two-layer routable, where n is the number of nets. Applying this algorithm repeatedly, we can find, in O(n3) time, a maximal subset of nets which is two-layer routable.

The VSTEP concept and its practical application in the form of an LED-type pnpn-VSTEP demonstrating low power consumption through electro-photonic operational modes are both shown. Further, with focus primarily on the new laser-mode VSTEP with high-intensity light output and narrow optical beam divergence, the design features such as threshold gain and optical absorptivity, device fabrication, and characteristics are explained. The possibility of ultimate performance based mainly on electrical to optical power conversion efficiency, important from the application viewpoint of optical interconnection, are also discussed. Also, as two examples of functional optical interconnection achieved by VSTEP, serial-to-parallel data conversion and optical self-routing switches are shown. Finally, future opto-electronic technologies to be developed for two-dimensionally integrable surface-type optical semiconductor devices, including the VSTEP, are discussed.

It is known that the problem of finding a largest common subgraph is NP-hard for general graphs even if the number of input graphs is two. It is also known that the problem can be solved in polynomial time if the input is restricted to two trees. In this paper, a randomized parallel (an RNC) algorithm for finding a largest common subtree of two trees is presented. The dynamic tree contraction technique and the RNC minimum weight perfect matching algorithm are used to obtain the RNC algorithm. Moreover, an efficient NC algorithm is presented in the case where input trees are of bounded vertex degree. It works in O(log(n1)log(n2)) time using O(n1n2) processors on a CREW PRAM, where n1 and n2 denote the numbers of vertices of input trees. It is also proved that the problem is NP-hard if the number of input trees is more than two. The three dimensional matching problem, a well known NP-complete problem, is reduced to the problem of finding a largest common subtree of three trees.

Multiple context-free grammars (mcfg's) are a subclass of generalized context-free grammars introduced by Pollard in order to describe the syntax of natural languages. First, this paper shows that the universal recognition problem for mcfg's is EXP-POLY time-complete, where the universal recognition problem is the one to decide whether G generates w for a given grammar G and string w. Next, it is shown that the problem for linear context-free rewriting systems introduced by Vijay-Shanker et al., which is a proper subclass of mcfg's, is PSPACE-complete.

The semantics of a language for communicating processes is investigated, and three full abstractness results for are established. The language contains atomic actions, termination, inaction, sequential composition, alternative composition, parallel composition, action restriction, and a form of guarded recursion. (The guardedness restriction on recursion is needed to establish one of the full abstractness results.) Three Plotkin-style operational semantics WL, CWL, and IWL of the language are defined. These semantics are linear in that the meaning of each program in any of these semantics is a set of action sequences the program may perform, and are weak in that the action sequences are obtained by ignoring (finte sequences of) internal moves. All the three semantics distinguish divergence (an infinite sequence of internal moves) from deadlock. The semantics IWL differs from the other two in that IWL is a so-called interal action semantics taking into account only internal moves under the assumption that the environment allows no (external) communication actions, and hence, the only possible actions for processes are internal moves, whereas the other two semantics take into account communication actions in addition to internal moves. The two semantics WL and CWL differ each other in that CWL is a so- called completed trace semantics, whereas WL is not. Then, two compositional models RF and IRF for the language are proposed, and the full a bstractness of RF (resp. of IRF) w. r. t. WL and CWL (resp. w. r. t. IWL), as expressed in the following, is established:s1s2(*) S[][S[]is a context of ⇒S[s1]S[s2]],where ,RF,WL, RF,CWL, IRF,IWL. A similar full abstractness result has been established by Bergstra, Klop, and Olderog for a language without recursion or internal moves. Moreover, Rutten investigated the semantics of a language similar to , in the framework of complete metric spaces, and showed that the failures model is fully abstract w. r. t. a strong linear semantics L, where L is strong in that it does not abstract from internal moves. The full abstractness of RF w. r. t. CWL, expressed in (*) with ,RF,CWL, is an extension of the result of Bergstra et al. to a language with recursion and internal moves. Also, the full abstractness of IRF w. r. t. IWL, expressed in (*) with ,IRF,IWL, is an extension of the Rutten's result, to the case of weak linear semantics with divergence.

We describe two information disseminating schemes, t-disseminate and t-Rdisseminate in a computer network with N processors, where each processor can send a message to t-directions at each round. If no processors have failed, these schemes are time optimal. When at most t processors have failed, for t1 and t2 any of these schemes can broadcast information within any consecutive logt+1N2 rounds, and for an arbitrary t they can broadcast information within any consecutive logt+1N3 rounds.

Circuit complexity of a Boolean function is defined to be the minimum number of gates in circuits computing the function. In general, the circuit complexity is established by deriving two types of bounds on the complexity. On one hand, an upper bound is derived by showing a circuit, of the size given by the bound, to compute a function. On the other hand, a lower bound is established by proving that a function can not be computed by any circuit of the size. There has been much success in obtaining good upper bounds, while in spite of much efforts few progress has been made toward establishing strong lower bounds. In this paper, after surveying general results concerning circuit complexity for Boolean functions, we explain recent results about lower bounds, focusing on the method of approximation.

The nonlinear optical properties of organics with unsaturated bonds were compared with those of inorganics including semiconductors and dielectrics. Because of the mesomeric effect, namely quantum mechanical resonance effect among configurations, aromatic molecules and polymers have larger optical nonlinear parameters defined as δ(n)X(n)/(X(1))n both for the second (n2) and third-order (n3) nonlinearities. Experimental results of ultrafast nonlinear response of conjugated polymers, especially polydiacetylenes, were described and a model is proposed to explain the relaxation processes of photoexcitations in the conjugated polymers. Applying the model constructed on the basis of the extensive experimental study, we propose model polymers to obtain ultrafast resonant optical nonlinearity.

By adding some functions to memories, highly parallel computation may be realized. We have proposed memory-based parallel computation models, which uses a new functional memory as a SIMD type parallel computation engine. In this paper, we consider models with communication between the words of the functional memory. The memory-based parallel computation model consists of a random access machine and a functional memory. On the functional memory, it is possible to access multiple words in parallel according to the partial match with their memory addresses. The cube-FRAM model, which we propose in this paper, has a hypercube network on the functional memory. We prove that PSPACE is accelerated to polynomial time on the model. We think that the operations on each word of the functional memory are, in a sense, the essential ones for SIMD type parallel computation to realize the computational power.

We study the depth of planar Boolean circuits. We show that planar Boolean circuits of depth D(n) are simulated by on-line Turing machines in space O(D(n)). From this relationship, it is shown that any planar circuit for computing integer multiplication requires linear depth. It is also shown that a planar analogue to the NC-hierarchy is properly separated.

There have been several studies related to a reduction of the amount of computational resources used by Turing machines. As consequences, Linear speed-up theorem", tape compression theorem" and reversal reduction theorem" have been obtained. In this paper, we discuss a leaf reduction theorem on alternating Turing machines. Recently, the result that one can reduce the number of leaves by a constant factor without increasing the space complexity was shown for space- and leaf-bounded alternating Turing machines. We show that for time- and leaf-bounded alternating Turing machines, the number of leaves can be reduced by a constant factor without increasing time used by the machine. Therefore, our result says that a constant factor on the leaf complexity does not affect the power of time- and leaf-bounded alternating Turing machines.

A maximal l-diameter tree cover of a graph G(V,E) is a spanning subgraph C(V,EC) of G such that each connected component of C is a tree, C contains no path with more than l edges, and adding any edge in EEC to C yields either a path of length l1 or a cycle. For every function f from positive integers to positive integers, the maximal f-diameter tree cover prolem (MDTC(f) problem for short) is to find a maximal f(n)-diameter tree cover of G, given an n-node graph G. In this paper, we give two parallel algorithms for the MDTC(f) problem. The first algorithm can be implemented in time O(TMSP(n,f(n))log2n) using polynomial number of processors on an EREW PRAM, where TMSP(n,f(n) is the time needed to find a maximal set of vertex disjoint paths of length f(n) in a given n-node graph using polynomial number of processors on an EREW PRAM. We then show that if suitable restrictions are imposed on the input graph and/or on the magnitude of f, then TMSP(n,f(n))O(logkn) for some constant k and thus, for such cases, we obtain an NC algorithm for the MDTC(f) problem. The second algorithm runs in time O(n log2n/{f(n)1}) using polynomial number of processors on an EREW PRAM. Thus if f(n)Ω(n/logkn) for some kO, we obtain an NC algorithm for the MDTC(f) problem.

A method is presented for analyzing the scalar wave scattering from a conducting target of arbitrary shape in random media for both the Dirichlet and Neumann problems. The current generators on the target are introduced and expressed generally by the Yasuura method. When using the current generators, the scattering problem is reduced to the wave propagation problem in random media.

This paper concerns a subclass of regular languages, called strictly regular languages, and studies the problem of identifying the class of strictly regular languages in the limit from positive data. We show that the class of strictly regular languages (SRLs) is polynomial time identifiable in the limit from positive data. That is, there is an algorithm that, for any strictly regular language L, identifies a finite automaton accepting L, called a strictly deterministic finite automaton (SDFA) in the limit from positive data, satisfying the property that the time for updating a conjecture is bounded by O(mN2), where m is the cardinality of the alphabet for L and N is the sum of lengths of all positive data provided. This is in contrast with the fact that the class of regular languages is not identifiable in the limit from positive data.

A rigorous theoretical method for predicting "ratio of desired signal power to interference power [c/i]" and "ratio of signal power to noise plus interference power [c/(n+i)]" where both desired and interference signals vary with time under the Nakagami-Rice fading conditions is presented. An alternative simple prediction method which is more desirable from the viewpoint of engineering application is then proposed. Prediction errors given by the simple method are evaluated by comparing to the errors given by the rigorous method, and it is confirmed that the simple method gives reasonable accuracy. This method is expected to serve in the development of frequency re-use technologies and the coordination of various systems for mobile satellite communications in the near future.

This paper describes the future perspective of automatic telephone interpretation using a multimedia intelligent communication network. The need for language interpretation over a telecommunication system creates a strong drive toward integrating information modalities for voice, image, data, computation and conferencing into modern systems using the capability of language interpretation. An automatic telephone interpretation system will solve the problems of language differences in international human-to-human communication. The future prospective of advanced multimedia language communication will be stated as the versatile application of an integrated intelligent network.

Transmittance distribution along a horizontal line in LCDs addressed by amorphous silicon TFTs was investigated using measurements and calculations. Nonuniformity of the distribution, in which the transmittance increased with increasing distance from the left edge of the LCD, was observed in a 10 inch diagonal TFT-LCD. The cause of the nonuniformity was attributed to the decrease in voltage drop due to the gate source parasitic capacitance and the increase in gate voltage fall time due to large line resistance, based on the measurements of voltage drops in TFT test elements and calculations considering the decrease in voltage drop. The distribution could be improved by reducing the line resistance and parasitic capacitance in the actual LCD.

We study the computational power of PC=P. We give a characterization of the class via single Turing machines. Based on the characterization, we give combinatorial problems that are Pm-complete for the class.

This paper describes the research results of three dimensional parameter representation of human arm motion, image synthesis and intelligent transmission for sign language communication between Japan and China using a personal computer.