In this paper, we show that without any unproven assumption, there exists a "four" move blackbox simulation perfect zero-knowledge interactive proof system of computational ability for any random self-reducible relation R whose domain is in BPP, and that without any unproven assumption, there exists a "four" move blackbox simulation perfect zero-knowledge interactive proof system of knowledge on the prime factorization. These results are optimal in the light of the round complexity, because it is shown that if a relation R has a three move blackbox simulation (perfect) zero-knowledge interactive proof system of computational ability (or of knowledge), then there exists a probabilistic polynomial time algorithm that on input x ∈ {0, 1}*, outputs y such that (x, y)∈R with overwhelming probability if x ∈dom R, and outputs "⊥" with probability 1 if x dom R.

We propose a fully digital architecture for Kohonen network suitable for VLSI implementation. The proposed architecture adopts a functional memory type parallel processor (FMPP) architecture which has a structure similar to a content addressable memory (CAM). One word of CAM is regarded as a processing element and a group of elements forms a neuron. All processing elements execute the same operation in bit-serial but in processor-parallel. Thus the number of instructions for realizing the network algorithm is independent of the number of neurons in the network. With reference to a previously reported CAM, we estimate a network with 96 neurons for speech recognition could be integrated on three chips using a 1.2 µm process, and it operates 50 times faster than a sequential hardware. Owing to its highly regular structure of memories, the proposed hardware architecture is well compatible with current VLSI technology.

By a measure we mean a function µ from {0, 1}* (the set of all binary sequences) to real numbers such that µ(x)0 and µ({0, 1}*). A malign measure is a measure such that if an input x in {0, 1}n (the set of all binary sequences of length n) is selected with the probability µ(x)/µ ({0, 1}n) then the worst-case computation time tWOA (n) and the average-case computation time tav,µA(n) of an algorithm A for inputs of length n are functions of n of the same order for any algorithm A. Li and Vitányi found that measures that are known as a priori measures are malign. We prove that a priori" -ness and malignness are different in one strong sense.

The hierarchies of multihead finite automata over a one-letter alphabet are investigated. Let SeH(k) [NSeH(k) ] denote the class of languages over a one-letter alphabet accepted by deterministic [nondeterministic] sensing two-way k-head finite automata. Let H (k)s[NH(k)s] denote the class of sets of square tapes over a one-letter alphabet accepted by two-dimensional four-way deterministic [nondeterministic] k-head finite automata. Let SeH(k)s[NSeH(k)s] denote the class of sets of square tapes over a one-letter alphabet accepted by two-dimensional four-way sensing deterministic [nondeterministic] k-head finite automata. This paper shows that SeH(k) SeH(k1) and NSeH(k) NSeH(k1) hold for all k3. It is also shown that H(k)s[NH(k)s] H(k1)s[NH (k1)s] and SeH (k)s[NSeH(k)s] SeH(k1)s[NSeH(k1)s] hold for all k1.

A priori estimation is presented for a computational complexity of the homotopy method applying to a certain class of strongly monotone nonlinear equations. In the present papers, a condition is presented for a certain class of uniquely solvable equations, under which an upper bound of a computational complexity of the Newton type homotopy method can be a priori estimated. In this paper, a condition is considered in a case of linear homotopy equations including the Newton type homotopy equations. In the first place, the homotopy algorithm based on the simplified Newton method is introduced. Then by using Urabe type theorem, which gives a sufficient condition guaranteeing the convergence of the simplified Newton method, a condition is presented under which an upper bound of a computational complexity of the algorithm can be a priori estimated, when it is applied to a certain class of strongly monotone nonlinear equations. The presented condition is demonstrated by numerical experiments.

The subject of the paper is to propose an O(|V|+|E|) algorithm for the 3-edge-connectivity augmentation problem (UW-3-ECA) defined by "Given an undirected graph G0=(V,E), find an edge set E of minimum cardinality such that the graph (V,EE ) (denoted as G0+E ) is 3-edge-connected, where each edge of E connects distinct vertices of V." Such a set E is called a solution to the problem. Let UW-3-ECA(S) (UW-3-ECA(M), respectively) denote UW-3-ECA in which G0+E is required to be simple (G0+E may have multiple edges). Note that we can assume that G0 is simple in UW-3-ECA(S). UW-3-ECA(M) is divided into two subproblems (1) and (2) as follows: (1) finding all k-edge-connected components of a given graph for every k3, and (2) determining a minimum set of edges whose addition to G0 result in a 3-edge-connected graph. Concerning the subproblem (1), we use an O(|V|+|E|) algorithm that has already been existing. The paper proposes an O(|V|+|E|) algorithm for the subproblem (2). Combining these algorithms makes an O(|V|+|E|) algorithm for finding a solution to UW-3-ECA(M). Furthermore, it is shown that a solution E to UW-3-ECA(M) is also a solution to UW-3-ECA(S) if |V|4, partly solving an open problem UW-k-ECA(S) that is a generalization of UW-3-ECA(S).

In this paper, we discuss secure protocols for shared computation of algorithms associated with digital signature schemes based on discrete logarithms. Generic solutions to the problem of cooperatively computing arbitraty functions, though formally provable according to strict security notions, are inefficient in terms of communication--bits and rounds of interaction--; practical protocols for shared computation of particular functions, on the other hand, are often shown secure according to weaker notions of security. We propose efficient secure protocols to share the generation of keys and signatures in the digital signature schemes introduced by Schnorr (1989) and ElGamal (1985). The protocols are built on a protocol for non-interactive verifiable secret sharing (Feldman, 1987) and a novel construction for non-interactively multiplying secretly shared values. Together with the non-interactive protocols for shared generation of RSA signatures introduced by Desmedt and Frankel (1991), the results presented here show that practical signature schemes can be efficiently shared.

In this paper, we propose an algorithm of O(|V|min{k,|V|,|A|}|A|) time complexity for finding all k-edge-connected components of a given digraph D=(V,A) and a positive integer k. When D is symmetric, incorporating a preprocessing reduces this time complexity to O(|A|+|V|2+|V|min{k,|V|}min{k|V|,|A|}), which is at most O(|A|+k2|V|2).

We have developed a new functional MOS transistor called Neuron MOSFET (abbreviated as neuMOS or νMOS) which simulates the function of biological neurons. The new transistor is capable of executing a weighted sum calculation of multiple input signals and threshold operation based on the result of weighted summation, all in the voltage mode at a single transistor level. By utilizing its neuron-like very powerful functional capability, various circuits essential for multiple-valued logic operation have been designed using quite simple circuit configurations. The circuit designs for data conversion between the multivalued and binary logic systems and for generating universal literal functions are described and their experimental verifications are presented. One of the most important features of νMOS multivalued lagic circuit is that the circuit operates basically in the voltage mode, thus greatly reducing the power dissipation as compared to the conventional current mode circuitry. This is indeed most essential in implementing multivalued logic systems in ultra large scale integration. Another important feature of νMOS design is in its flexibility of implementing logic functions. The functional form of a universal literal function, for instance, can be arbitrarily altered by external signals without any modifications in its hardware configuration. A circuit representing multiple-valued multithreshold functions is also proposed.

Some problems in formal language theory are considered and are shown to be deterministic exponential time complete. They include the problems for a given context-free grammar G, a nondeterministic finite automaton M, a deterministic pushdown automaton MD, of determining whether L(G)L(M), and whether L(MD)L(M). Polynomial time reductions are presented from the pebble game problem, known to be deterministic exponential time complete, to each of these problems.

Two computational-geometric approaches to linear programming are surveyed. One is based on the prune-and-search paradigm and the other utilizes randomization. These two techniques are quite useful to solve geometric problems efficiently, and have many other applications, some of which are also mentioned.

Let C{c1, , cm} be a family of subsets of a finite set S{1, , n}, a subset S of S is a co-hitting set if S contains no element of C as a subset. By using an O((log n)2) time EREW PRAM algorithm for a maximal independent set problem (MIS), we show that a maximal co-hitting set for S can be computed on an EREW PRAN in time O(αβ(log(nm))2) using O(n2 m) processors, where αmax{|cii1, , n} and βmax{|djj1, , n} with dj{ci|jci}. This implies that if αβO((log(nm))k) then the problem is solvable in NC.

The future trends of optical technologies combined with LSI are reviewed. Present problems of LSI, and the possible solutions to these problems through the merger of the optical technology into LSI are discussed. One of the present trends in interconnection between LSI components is the timeserial approach, originally developed for the optical communication. This method is capable of high speed data transfer. The other is a space-parallel approach, arising from the two-dimensional nature of the light propagation. This approach has the capability of performing parallel processing. A hybrid OEIC, possibly on GaAs, is discussed as an example of future photonic LSI. The lack of key devices is a fundamental barrier to the future improvement of photonic LSI. Direct interaction between photons and electrons is a promissing approach. Some of the Author's ideas to promote the merger of photonics and LSI are proposed.

Separability is a valuable property of nonlinear mappings. By exploiting this property, computational complexity of many numerical algorithms can be substantially reduced. In this letter, a new algorithm is presented that detects the separability of nonlinear mappings using the concept of "computational graph". A hybrid algorithm using both the top-down search and the bottom-up search is proposed. It is shown that this hybrid algorithm is advantageous in detecting the separability of nonlinear simultaneous functions.

This paper deals with the sub-problems of generating a mask pattern from the logical description of a large-scale CMOS circuit. The large-scale layout can be generated in divide-and-conquer style: divide a given circuit into a set of sub-circuits, generate the layout of each sub-circuit, and merge the resulting layouts to create the whole layout. This paper proposes a layout synthesis algorithm for a sub-circuit with physical constraints for the synthesis scheme above. The physical constraints considered here are the relative placement of logic cells (sets of logic gates) and the routing constraint based on the costs of wiring layers and vias. These constraints will be given by the global optimizer in a two-dimensional layout synthesis routine, and they should be kept at the subsequent one-dimensional layout synthesis for a sub-circuit. The latter is also given for enhancing the circuit performance by limiting the usage of wiring layers and vias for special net such as a clock net. The placement constraint is maintained using PQ-tree, a tree structure representing a set of restricted permutations of elements. One-dimensional layout synthesis determines the placement of transistors by the enhanced pairwise exchanging method under the PQ-tree representation. The routing constraints is considered in the newly developed line-search routing method using a cost-based searching. Experimental results for practical standard cells, including up to 200 transistors, prove that the algorithms can produce the layouts comparable to handcrafted cells. Also on a two-dimensional layout synthesis using the algorithms, the results for benchmark circuits of Physical Design Workshop 1989, i.e., MCNC benchmark circuits, are superior to the best results exhibited at Design Automation Conference 1990.

A novel harmonic retrieval algorithm is proposed in this paper based on Hopfield's neural network. Frequencies can be retrieved with high accuracy and high resolution under low signal to noise ratio (SNR). Amplitudes and phases in harmonic signals can also be estimated roughly by an energy constrained linear projection approach as proposed in the algorithm. Only no less than 2q neurons are necessary in order to detect harmonic siglnals with q different frequencies, where q denotes the number of different frequencies in harmonic signals. Experimental simulations show fast convergence and stable solution in spite of low signal to noise ratio can be obtained using the proposed algorithm.

The elementary formal system (EFS, for short) is a kind of logic program which directly manipulates character strings. This paper outlines in brief the authors' studies on algorithmic learning theory developed in the framework of EFS's. We define two important classes of EFS's and a new hierarchy of various language classes. Then we discuss EFS's as logic programs. We show that EFS's form a good framework for inductive inference of languages by presenting model inference system for EFS's in Shapiro's sense. Using the framework we also show that inductive inference from positive data and PAC-learning are both much more powerful than they have been believed. We illustrate an application of our theoretical results to Molecular Biology.

We investigate the relationship between two different notions of reducibility among prediction (learning) problems within the distribution-free learning model of Valiant (PAC learning model). The notions of reducibility we consider are the analogues for prediction problems of the many-one reducibility and of the Turing reducibility. The former is the notion of prediction preserving reducibility developed by Pitt and Warmuth, and its generalization. Concerning these two notions of reducibility, we show that there exist a pair of prediction problems A and B, whose membership problems are polynomial time solvable, such that A is reducible to B with respect to the Turing reducibility, but not with respect to the prediction preserving reducibility. We show this result by making use of the notion of a class of polynomially sparse variants of a concept representation class. We first show that any class A of polynomially sparse variants of another class B is reducible to B with respect to the Turing reducibility'. We then prove the existence of a prediction problem R and a class R of polynomially sparse variants of R, such that R does not reduce to R with respect to the prediction preserving reducibility.

In the approximate learning model introduced by Valiant, it has been shown by Blumer et al. that an Occam algorithm is immediately a PAC-learning algorithm. An Occam algorithm is a polynomial time algorithm that produces, for any sequence of examples, a simple hypothesis consistent with the examples. So an Occam algorithm is thought of as a procedure that compresses information in the examples. Weakening the compressing ability of Occam algorithms, a notion of weak Occam algorithms is introduced and the relationship between weak Occam algorithms and PAC-learning algorithms is investigated. It is shown that although a weak Occam algorithm is immediately a (probably) consistent PAC-learning algorithm, the converse does not hold. On the other hand, we show how to construct a weak Occam algorithm from a PAC-learning algorithm under some natural conditions. This result implies the equivalence between the existence of a weak Occam algorithm and that of a PAC-learning algorithm. Since the weak Occam algorithms constructed from PAC-learning algorithms are deterministic, our result improves a result of Board and Pitt's that the existence of a PAC-learning algorithm is equivalent to that of a randomized Occam algorithm.

Parallel multiple context-free grammars (pmcfg's) and multiple context-free grammars (mcfg's) were introduced as extensions of context-free grammars to describe the syntax of natural languages. Pmcfg's and mcfg's deal with tuples of strings, and it has been shown that the universal recognition problem for mcfg's is EXP-POLY time-complete where the universal recognition problem is the problem to decide whether G generates w for a given grammar G and string w. In this paper, the universal recognition problems for the class of pmcfg's and for the subclass of pmcfg's with the information-lossless condition are shown to be EXP-POLY time-complete and PSPACE-complete, respectively. It is also shown that the problems for pmcfg's and for mcfg's with a bounded dimension are both -complete and those for pmcfg's and for mcfg's with a bounded degree are both -complete. As a corollary, the problem for modified head grammars introduced by Vijay-Shanker, et al. to define the syntax of natural languages is shown to be in deterministic polynomial time.