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.

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 log_t+1N2 rounds, and for an arbitrary t they can broadcast information within any consecutive log_t+1N3 rounds.

A maximal l-diameter tree cover of a graph G(V,E) is a spanning subgraph C(V,E_C) 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 EE_C 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(T_MSP(n,f(n))log²n) using polynomial number of processors on an EREW PRAM, where T_MSP(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 T_MSP(n,f(n))O(log^kn) 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 log²n/{f(n)1}) using polynomial number of processors on an EREW PRAM. Thus if f(n)Ω(n/log^kn) for some kO, we obtain an NC algorithm for the MDTC(f) problem.

In this paper we study the problem of scheduling a tree-structured program on multiprocessors so as to minimize the total execution time, which includes communication delay between processors. It is assumed in the problem that a sufficiently large number of processors are available. It is known that if the program structures are restricted to be out-trees, the problem can be solved in O(n²) time, where n denotes the number of modules of a program. However, this problem is known to be NP-hard if the program structures are allowed to be in-trees. Up to now, no optimal algorithm, except an obvious one, was known for the latter case while some approximation algorithms were shown. We present an optimization algorithm with a nontrivial time bound O((1.52)ⁿn log n) for the in-tree case.

We study the computational power of P^C₌P. We give a characterization of the class via single Turing machines. Based on the characterization, we give combinatorial problems that are ^P_m-complete for the class.

We propose two types of public-key cryptographic schemes based on elliptic curves modulo n, where n is the product of secret large primes p and q. The RSA-type scheme has an encryption function with an odd multiplier. The Rabin-type scheme has an encryption function with a multiplier of 2. The security of the proposed schemes is based on the difficulty of factoring n. Other security characteristics are also discussed. We show some applications to a master key scheme and blind signature scheme.

A chordal ring network is a processor network on which n processors are arranged to a ring with additional chords. We study a distributed leader election algorithm on chordal ring networks and present trade-offs between the message complexity and the number of chords at each processor and between the message complexity and the length of chords as follows:For every d(1dlog^* n1) there exists a chordal ring network with d chords at each processor on which the message complexity for leader election is O(n(log^(d1)nlog^* n)).For every d(1dlog^* n1) there exists a chordal ring network with log^(d1)nd1 chords at each processor on which the message complexity for leader election is O(dn).For every m(2mn/2) there exists a chordal ring network whose chords have at most length m such that the message complexity for leader election is O((n/m)log n).

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, ^C_WL, and ^I_WL 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 ^I_WL differs from the other two in that ^I_WL 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 ^C_WL differ each other in that ^C_WL is a so- called completed trace semantics, whereas _WL is not. Then, two compositional models _RF and ^I_RF for the language are proposed, and the full a bstractness of _RF (resp. of ^I_RF) w. r. t. _WL and ^C_WL (resp. w. r. t. ^I_WL), as expressed in the following, is established:s₁s₂(*) S[][S[]is a context of ⇒S[s₁]S[s₂]],where ,_RF,_WL, _RF,^C_WL, ^I_RF,^I_WL. 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. ^C_WL, expressed in (*) with ,_RF,^C_WL, is an extension of the result of Bergstra et al. to a language with recursion and internal moves. Also, the full abstractness of ^I_RF w. r. t. ^I_WL, expressed in (*) with ,^I_RF,^I_WL, is an extension of the Rutten's result, to the case of weak linear semantics with divergence.

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.

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.

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(n₁)log(n₂)) time using O(n₁n₂) processors on a CREW PRAM, where n₁ and n₂ 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.

This paper proposes a new construction of the minimum knowledge undeniable signature scheme which solves a problem inherent in Chaum's scheme. We formulate a new proof system, the minimum knowledge interactive bi-proof system, and a pair of languages, the common witness problem, based on the random self-reducible problem. We show that any common witness problem has the minimum knowledge interactive bi-proof system. A practical construction for undeniable signature schemes is proposed based on such a proof system. These schemes provide signature confirmation and disavowal with the same protocol (or at the same time).

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.

In this paper, some classes of arithmetic circuits are introduced that capture the computational complexity of computing the determinant of matrices with entries either indeterminates or constants from a field. An arithmetic circuit is just like a Boolean circuit, except that all AND and OR gates (with fan-in two) are replaced by gates realizing a multiplication and an addition, respectively, of two polynomials over some indeterminates with coefficients from the field, and the circuit computes a (formal multivariate) polynomial in the obvious sense. An arithmetic circuit is said to be skew if at least one of the inputs of each multiplication gate is either an indeterminate or a constant. Then it is shown that for all square matrices M of dimension q, the determinant of M can be computed by a skew arithmetic circuit of (q²⁰) gates, and is shown that for all skew arithmetic circuits C of size q, the polynomial computed by C can be defined as the determinant of a square matrix M of dimension (q). Thus the size of skew arithmetic circuit is polynomially related to the dimension of square matrices when it is considered to represent multivariate polynomials in both arithmetic circuits and the determinant. The results are extended to some other classes of arithmetic circuits less restricted than skew ones, and by using such an extended result, a difference and a similarity are demonstrated between polynomials represented as the determinant of matrix of relatively small dimension and those polynomials computed by arithmetic formulas and arithmetic circuits of relatively small size and degree.

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(mN²), 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.

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 reversible (or injective) cellular automaton (RCA) is a backward deterministic" CA, i.e., every configuration of it has at most one predecessor. Margolus has been shown that there is a computation-universal two-dimensional 2-state RCA model. Although his model is very interesting, it differs from a standard CA model because of its somewhat spatial and temporal non-uniformity. In this paper, we present two kinds of simple 16-state computation-universal models using the framework of two-dimensional reversible partitioned CA (PCA). Since PCA can be considered as a subclass of standard CA, we can immediately obtain 16-state standard RCA models from them. For each of these models, we designed a configuration which simulates a Fredkin gate. Since Fredkin gate has been known to be a universal logic element, computation-universality of these two models is concluded.

In this paper, we present a new image compression scheme, Projection-VQ, based on reconstruction from vector quantized projections. We can easily deal with the blocks of larger size in Projection-VQ than in conventional VQ schemes, because the dimension of vectors in projection domain is, in general, much smaller than that in the spatial domain. In Projection-VQ, the image can be reconstructed without destroying edge sharpness in the process since the projection data having the edge information are preferentially transmitted. There are several good algorithms of reconstructing an image from projections. However, we use a new modified reconstruction algorithm suitable for a variable bit rate image coding system. We allocate the bits depending on the characteristics of the block images. Our simulation results show that the performances are superior to the ordinary VQ schemes in PSNR, and that the improvement in subjective image quality is substantial.

This paper proposes a knowledge-based design method of a protocol of a communication network system based on the knowledge-based design methodology for computer communication systems. In the proposed method, two knowledge models, i.e., the communication network architecture model (CNAM) and the communication protocol architecture model (CPAM), are introduced and a protocol design task is modeled as a successive transformation process of these knowledge models. Giving CNAM which represents the users' requirements concerning a communication network system, the requirements specification of a protocol is derived from CNAM and represented as CPAM. Then, the detailed requirements specification of a protocol is also derived from CPAM and represented by the formal description technique (FDT-Expressions). The derivations of CPAM and FDT-Expressions are executed by the transformation rules which represent the mappings between knowledge models. Due to formally defined knowledge models and mappings, the proposed method provides a framework of a systematic support of knowledge-based protocol design. In this paper, the formal definitions of CNAM and CPAM are given, then the derivation process of FDT-Expressions of a protocol is also formalized based on these knowledge models. Furthermore, a design example is demonstrated by using LOTOS as one of the FDT-Expressions of a protocol.

This paper presents a new connected associative memory neural network. In this network, a threshold function which has two dynamical parameters is introduced. After analyzing the dynamical behaviors and giving an upper bound of the memory capacity of the conventional connected associative memory neural network, it is demonstrated that these parameters play an important role in the recalling processes of the connected neural network. An approximate method of evaluationg their optimum values is given. Further, the optimum feedback stopping time of this network is discussed. Therefore, in our network, the recalling processes are ended at the optimum feedback stopping time whether a state energy has been local minimum or not. The simulations on computer show that the dynamical behaviors of our network are greatly improved. Even though the number of learned patterns is so large as the number of neurons, the statistical properties of the dynamical behaviors of our network are that the output series of recalling processes approach to the expected patterns on their initial inputs.