ACk is the class of problems solvable by an alternating Turing machine in space O(log n) and alternation depth O(logk n) [S. A. Cook, A taxonomy of problems with fast parallel algorithms, Inform. Contr. vol. 64]. We consider a game played by two persons: each player alternately moves a marker along an edge of a given digraph, and the first palyer who cannot move loses the game. It is shown that the problem to determine whether the first player can win the game on a digraph with n nodes exactly after logk n moves is complete for ACk nuder NC1 reducibility.

We have made an exhaustive computation to establish that 33 comparisons never sort 13 items. The computation was carried out within 10 days by a workstation. Since merge insertion sort [Ford, et al. A tournament problem, Amer. Math. Monthly, vol. 66, (1959)] uses 34 comparisons for sorting 13 items, our result guarantees the optimality of the sorting procedure to sort 13 items as far as the number of comparisons is concerned. The problem has been open for nearly three decades since Mark Wells discovered that 30 comparisons are required to sort 12 items in 1965.

Learning correctly from queries" is a formal learning model proposed by Angluin. In this model, for a class Γ of language representations, a learner asks queries to a teacher of an unknown language Lq which can be represented by some GqΓ, and eventually outputs a language representation GΓ which represents Lq and halts. An algorithm (leaner) A is said to learn a class of languages represented by Γ in the weak definition if the time complexity of A is some polynomial of n and m, where n is the minimum size of the lagunage representations in Γ which represent Lq, and m is the maximum length of the counterexamples returned in an execution. On the other band, A is said to learn represented by Γ in the strong definition if at any point τ of the execution, the time consumed up to τ is some polynomial of n and m, where n is the same as above, and m is the maximum length of the counterexamples returned up to τ. In this paper, adequacy of the model is examined, and it is shown that both in the weak and strong definitions, there exist learners which extract a long counterexample, and identify Lq by using equivalence queries exhaustively. For example, there exists a learner which learns the class CFL of context-free languages represented by the class CFG of context-free grammars in the weak definition using only equivalence queries. Next, two restrictions concerning with learnability criteria are introduced. Proper termination condition is that when a teacher replies with yes" to an equivalence query, then the learner must halt immediately. The other condition, called LBC-condition, is that in the weak/strong definition, the time complexity must be some polynomial of n and log m. In this paper, it is shown that under these conditions, there still exist learners which execute exhaustive search. For instance, there exists a learner which learns CFL represented by CFG in the weak definition using membership queries and equivalence queries under the proper termination condition, and there also exists a learner that learns CFL represented by CFG in the strong definition using subset queries and superset queries under LBC-condition. These results suggest that the weak definition is not an adequate learning model even if the proper termination condition is assumed. Also, the model becomes inadequate in the strong definition if some combination of queries, such as subset queries and superset queries, is used instead of equivalence queries. Many classes of languages become learnable by our extracting long counterexample" technique. However, it is still open whether or not CFL represented by CFG is learnable in the strong definition from membership queries and equivalence queries, although the answer is known to be negative if at least one of (1) quadratic residues modulo a composite, (2) inverting RSA encryption, or (3) factoring Blum integers, is intractable.

We propose a beam tracing frame which shifts together with either the guiding structure or the beam propagation in optical circuits. This frame is adaptive to the beam propagation analysis based on the finite-element method and can reduce the computational window size.

Finite state translation systems (fsts') are a widely studied computational model in the area of tree automata theory. In this paper, the string generating capacities of fsts' and their subclasses are studied. First, it is shown that the class of string languages generated by deterministic fsts' equals to that of parallel multiple context-free grammars, which are an extension of context-free grammars. As a corollary, it can be concluded that the recognition problem for a deterministic fsts is solvable in O(ne1)-time, where n is the length of an input word and e is a constant called the degree of the deterministic fsts'. In contrast to the latter fact, it is also shown that nondeterministic monadic fsts' with state-bound 2 can generate an NP-complete language.

An extension of the notion of cryptographically strong pseudo-random generator to a distributed setting is proposed in this paper. Instead of a deterministic function to generate a pseudo-random bit string from a truly random shorter string, we have a deterministic secure protocol for a group of separate entities to compute a secretly shared pseudo-random string from a secretly shared and truly random shorter string. We propose a precise definition of this notion in terms of Yao's computational entropy and describe a concrete construction using Shamir's pseudo-random number generator. Several practical applications are also discussed.

This document describes a proposal for the implementation of a new VLSI neural network technique called Parallel Propagated Targets (PPT). This technique differs from existing techniques because all layer, within a given network, can learn simultaneously and not sequentially as with the Back Propagation algorithm. the Parallel Propagated Target algorithm uses only information local to each layer and therefore there is no backward flow of information within the network. This allows a simplification in the system design and a reduction in the complexity of implementation, as well as acheiving greater efficiency in terms of computation. Since all synapses can be calculated simultaneously it is possible using the PPT neural algorithm, to parallelly compute all layers of a multi-layered network for the first time.

This paper presents an efficient algorithm for constructing at-most-k levels of an arrangement of n lines in the plane in time O(nk+n log n), which is optimal since Ω(nk) line segments are included there. The algorithm can sweep the at-most-k levels of the arrangement using O(n) space. Although Everett et al. recently gave an algorithm for constructing the at-most-k levels with the same time complexity independently, our algorithm is superior with respect to the space complexity as a sweep algorithm. Then, we apply the algorithm to a bipartitioning problem of a bichromatic point set： For r red points and b blue points in the plane and a directed line L, the figure of demerit fd(L) associated with L is defined to be the sum of the number of blue points below L and that of red ones above L. The problem we are going to consider is to find an optimal partitioning line to minimize the figure of demerit. Given a number k, our algorithm first determines whether there is a line whose figure of demerit is at most k, and further finds an optimal bipartitioning line if there is one. It runs in O(kn+n log n) time (n=r+b), which is subquadratic if k is sublinear.

The planar point location problem is one of the most fundamental problems in computational geometry and stated as follows： Given a straight line planar graph (subdivision) with n vertices and an arbitary query point Q, determine the region containing Q. Many algorithms have been proposed, and some of them are known to be theoretically optimal (O(log n) search time, O(n) space and O(n log n) preprocessing time). In this paper, we implement several representative algorithms in C, and investigate their practical efficiencies by computational experiments on Voronoi diagrams with 210 - 217 vertices.

This paper investigates the accepting powers of one-way alternating multi-stack-counter automata (lamsca's) and one-way alternating multi-counter automata (lamsca's) which operate in realtime. For each k1, let 1ASCA (k, real) (1ACA(k, real)) denote the class of sets accepted by realtime one-way alternating k-stach-counter (k-counter) automata, and let 1USCA(k, real)(1UCA(k, real)) denote the class of sets accepted by realtime one-way alternating k-stack-counter (k-counter) automata with only universal states. We first investigate a relationship between the accepting powers of realtime lamsca's (lamca's) with only universal states, with only existential states, and with full alternation. We then investigate hierarchical properties based on the numbers of counters and stackcounters, and show, for example, that for each k1, 1USCA(k+1, real)-1ASCA(k, real)φ and 1UCA(k+1, real)-1ACA(k, real)φ. We finally investigate a relationship between the accepting powers of realtime lamsca's and lamca's, and show, for example, that there are no i and j such that 1UCA(i, real)=1USCA(j, real), and 1USCA(k, real)-1ACA(k, real)φ for each k1.

In this paper, it is proven that the following three decision problems on validation of protocols with bounded capacity channels are NP-complete. (1) Given a protocol with the channel capacity being 1, determine whether or not there exist deadlocks in the protocol. (2) Given a protocol with the channel capacity being 1, determine whether or not there exist unspecified receptions in the protocol. (3) Given a protocol with the channel capacity being 2, determine whether or not there exist overflows such that the channel capacity is not bounded by 1 in the protocol. These results suggest that, even when all channeles in a protocol are bounded by 1 or 2, protocol validation should be in general interactable. It also clarifies the boundary of computational complexity of protocol validation problems because the channel capacity 0 does not allow protocols to transmit and recieve messages.

We propose a fast computation method of stochastic relaxation for the continuous-valued Markov random field (MRF) whose energy function is represented in the quadratic form. In the case of regularization in visual information processing, the probability density function of a state transition can be transformed to a Gaussian function, therefore, the probablistic state transition is realized with Gaussian random numbers whose mean value and variance are calculated based on the condition of the input data and the neighborhood. Early visual information processing can be represented with a coupled MRF model which consists of continuity and discontinuity processes. Each of the continuity or discontinuity processes represents a visual property, which is like an intensity pattern, or a discontinuity of the continuity process. Since most of the energy function for early visual information processing can be represented by the quadratic form in the continuity process, the probability density of local computation variables in the continuity process is equivalent to the Gaussian function. If we use this characteristic, it is not necessary for the discrimination function computation to calculate the summation of the probabilities corresponding to all possible states, therefore, the computation load for the state transition is drastically decreased. Furthermore, if the continuous-valued discontinuity process is introduced, the MRF model can directly represent the strength of discontinuity. Moreover, the discrimination function of this energy function in the discontinuity process, which is linear, can also be calculated without probability summation. In this paper, a fast method for calculating the state transition probability for the continuous-valued MRF on the visual informtion processing is theoretically explained. Next, initial condition dependency, computation time and dependency on the statistical estimation of the condition are investigated in comparison with conventional methods using the examples of the data restoration for a corrupted square wave and a corrupted one-dimensional slice of a natural image.

Persistent data structures, introduced by Sarnak and Tarjan, have been found especially useful in designing geometric algorithms. In this paper, we present a persistent form of binary-binary search tree, and then apply this data structure to solve various geometric searching problems, such as, three dimensional ray-shooting, hidden surface removal, polygonal point enclosure searching and so on. In all applications, we are able to either improve existing bounds or establish new bounds.

This paper investigates the properties of synchronized alternating one-way multicounter machines (lsamcm's) which operate in real time (lsamcm-real's) and whose leaf-sizes are bounded by a constant or some function of the length of an input. Leaf-size reflects the number of processors which run in parallel in scanning a given input. We first consider the hieracrchies of lsamcm-real's based on the number of counters and constant leaf-sizes. We next show that lsamcm-real's are less powerful than lsamcm's which operate in linear time when the leaf-sizes of these machines are bounded by a function L(n) such that limn[L(n) log n/n]0 and L(n)2.

This paper studies the problem of embedding a graph into a book with nodes on a line along the spine of the book and edges on the pages in such a way that no edge crosses another. Atneosen as well as Bernhart and Kainen has shown that every graph can be embedded into a 3-page book when each edge can be embedded in more than one page. The time complexity of Bernhart and Kainen's method is Ω(ν(G)), where ν(G) is the crossing number of a graph G. A new 0(mn) algorithm is derived in this paper for embedding a graph G=(V, E), where m=│E│ and n= │V│ . The number of points at which edges cross over the spine in embedding a complete graph into a 3-page book is also investigated.

Server aided secret computation (SASC) protocol also called the verifiable implicit asking protocol, is a protocol such that a powerful untrusted auxiliary device (server) can help a smart card (client) for computing a secret function efficiently. In this paper, we extend the concept of addition sequence to the secure addition sequence and develop an efficient algorithm to construct such sequence. By incorporating the secure addition sequence into the SASC protocol the performance of SASC protocol can be further enhanced.

This letter presents an algorithm named SPM which generates test patterns for single stuck-at faults in synchronous sequential circuits based on a product machine traversal method. The new idea presented in this letter is partitioned image computation combined with a mixed breadth-first/depth-first search. Image computation is carried out in partitioned manner by substituting constant logical values to some input variables. This brings about significant reduction in storage requirement during image computation. A test generator based on SPM achieved 100% fault efficiency for the ISCAS'89 benchmark circuits with not more than 32 flip-flops.

For each two positive integers r, s, let [1DCM(r)-Time(ns)] ([1NCM(r)-Time(ns)]) and [1DCM(r)-Space(ns)] ([1NCM(r)-Space(ns)]) be the classes of languages accepted in time ns and in space ns, respectively, by one-way deterministic (nondeterministic) r-counter machines. We show that for each X{D, N}, [1XCM(r)-Time(ns)][1XCM(r+1)-Time(ns)] and [1XCM(r)-Space(ns)][1XCM(r+1)-Space(ns)]. We also investigate the relationships between one-way multicounter machines and cooperating systems of one-way finite automata. In particular, it is shown that one-way (one-) counter machines and cooperating systems of two one-way finite automata are equivalent in accepting power.

A new Viterbi algorithm with adaptive path reduction method is presented. The proposed system consists of the pre-decoder and reduced path Virerbi decoder. The predecoder separates the mixed channel noise from the received sequence. The number of errors in the pre-decoded error sequence is counted and the path reduction is implemented by the number of errors in pre-decoded error sequence. The path reduction is implemented as a function of channel condition because the errors in the pre-decoded error sequence can be considered as the channel error sequence. Due to the reduction of the path, the number of ACS (add compare select) operations can be reduced, which occupies the dominant part in Viterbi decoding. The ACS reduction ratio for the proposed system achieves up to 30% for the case of (2, 1, 2) Ungerboeck code without degradation of the error performance.

In this paper we propose an architecture and an algorithm for the parallel execution of OPS5 production systems. It is known that current OPS5 production system interpreters spend almost 90% of their execution time in the match step. Thus, in this paper we focus on the speedup of the match step. The match algorithm used in OPS5 is called Rete and the algorithm uses a special kind of a date-flow network compiled from the left hand sides of rules. To achieve the maximum degree of parallelism of a given OPS5 program by as few processors as possible, the proposed parallel machine uses loosely coupled multiprocessors. Parallel machines designed for fine-grain parallelism, such as DADO, also use loosely coupled multiprocessors. However, the proposed machine differs from such machines at the following points: use of powerful processors which have large amounts of memories and small cycle times; use of a shared Rete network (parallel machines designed for fine-grain parallelism use an unshared Rete network); high hardware utilization. Basic ideas of the proposed parallel machine are as follows. (1) Use of a modified Rete network in which node sharing is used only for constant-test nodes and each memory node is lumped with the child two-input node. (2) Static allocation of the nodes of the modified Rete network onto processors. (3) Partition of the set of processors into three subsets: constant-test node processors, two-input node processors and conflict-set processors. (4) Use of a ring network for the interconnection network among two-input node processors. In addition to an architecture for parallel execution of OPS5 production systems, we propose a scheme for mapping the modified Rete network into the proposed architecture. The results of simulation experiments showed that the proposed architecture is promising for parallel execution of OPS5 production systems.