We consider a class of unknown scenes Sk(n) with rectangular obstacles aligned with the axes such that Euclidean distance between the start point and the target is n, and any side length of each obstacle is at most k. We propose a strategy called the adaptive-bias heuristic for navigating a robot in such a scene, and analyze its efficiency. We show that a ratio of the total distance walked by a robot using the strategy to the shortest path distance between the start point and the target is at most 1+(3/5) k, if k=o(n) and if the start point and the target are at the same horizontal level. This ratio is better than a ratio obtained by any strategy previously known in the class of scenes, Sk(n), such that k=o(n).

We propose two simple algorithms based on bounded tickets for the mutual exclusion problem on the asynchronous single-writer/multi-reader shared memory model. These algorithms are modifications of the Bakery algorithm. An unattractive property of the Bakery algorithm is that the size of its shared memory is unbounded. Initially we design a provisional algorithm based on bounded tickets. It guarantees mutual exclusion in the case where a certain condition is satisfied. To remove the condition, we use an additional process that does not correspond to any user. The algorithm with the additional process is a lockout-free mutual exclusion algorithm on the asynchronous single-writer/multi-reader shared memory model. We then modify this algorithm to reduce the shared memory size with the cost of using another additional process. The maximum waiting time using each of the algorithms proposed in this paper is bounded by (n-1)c+O(nl), where n is the number of users, l is an upper bound on the time between two successive atomic steps, and c is an upper bound on the time that any user spends using the resource. The shared memory size needed by the first algorithm and the second algorithm are (n+1)(1+log (4n)) bits and n(1+log (4n-4))+2 bits, respectively.

We propose two fault-tolerant broadcasting schemes in star graphs. One of the schemes can tolerate up to n2 faults of the crash type in the n-star graph. The other scheme can tolerate up to (n3d1)/2 faults of the Byzantine type in the n-star graph, where d is the smallest positive integer satisfying nd!. Each of the schemes is designed for the single-port mode, and it completes the broadcasting in O(n log n) time. These schemes are time optimal. For the former scheme we analyze the reliability in the case where faults of the crash type are randomly distributed. It can tolerate (n!)α faults randomly distributed in the n-star graph with a high probability, where α is any constant less than 1.

Using number theoretic properties we show the following results: For any k2, the language family generated by {akn|n in N}{ε} with trio and intersection operations contains {anbn|n in N}. If k is a multiple of 3 or 4, then the language family generated by {ank|n in N} with trio and intersection operations contains {anbn|n in N}. These language families are commutative.

A directed graph G = (V,E) is called the n-rotator graph if V = {a1a2an|a1a2an is a permutation of 1,2,,n} and E = {(a1a2an,b1b2bn)| for some 2 i n, b1b2bn = a2aia1ai+1an}. We show that for any pair of distinct nodes in the n-rotator graph, we can construct n - 1 disjoint paths, each length < 2n, connecting the two nodes. We propose a nonadaptive fault-tolerant file transmission algorithm which uses these disjoint paths. Then the probabilistic analysis of its reliability is given.

We propose the problem of how to transmit an information-theoretically secure bit using random deals of cards among players in hierarchical groups and a computationally unlimited eavesdropper. A player in the highest group wants to send players in lower groups a secret bit which is secure from the eavesdropper and some other players. We formalize this problem and design protocols for constructing secret key exchange spanning trees on hierarchical groups. For each protocol we give sufficient conditions to successfully construct a secret key exchange spanning tree for the hand sizes of the players and the eavesdropper.

We study robot navigation in unknown environment with rectangular obstacles aligned with the x and y axes. We propose a strategy called the modified-bian heuristic, and analyze its efficiency. Let n be the distance between the start point and the target of robot navigation, and let k be the maximum side length among the obstacles in a scene. We show that if k=(o(n) and if the summation of the widths of the obstacles on the line crossing the target and along the y axis is o(n), then ratio of the total distance walked by the robot to the shortest path length between the start point and the target is at most arbitrarily close to 1+k/2, as n grows. For the same restrictions as above on the sizes of the obstacles, the ratio is also at most arbitrarily close to 1+3/4n, as n grows, where is the summation of lengths of the obstacles in y axis direction.

A graph G is called an n-channel graph at vertex r if there are n independent spanning trees rooted at r. A graph G is called an n-channel graph if G is an n-channel graph at every vertex. Independent spanning trees of a graph play an important role in fault-tolerant broadcasting in the graph. In this paper we show that if G1 is an n1-channel graph and G2 is an n2-channel graph, then G1G2 is an (n1 + n2)-channel graph. We prove this fact by a construction of n1+n2 independent spanning trees of G1G2 from n1 independent spanning trees of G1 and n2 independent spanning trees of G2. As an application we describe a fault-tolerant broadcasting scheme along independent spanning trees.

An invertible length preserving transducer is called a weakly invertible finite automaton (WIFA for short). If the first letter of any input string of length τ + 1 is uniquely determined by the corresponding output string by a WIFA and its initial state, it is called a WIFA with delay τ. The composition of two WIFAs is the natural concatenation of them. The composition is also a WIFA whose delay is less than or equal to the sum of the delays of the two WIFAs. In this paper we derive various results on a decomposition of a WIFA into WIFAs with smaller delays. The motivation of this subject is from theoretical interests as well as an application to cryptosystems. In order to capture the essence of the decomposability problem, we concentrate on WIFAs such that their input alphabets and their output alphabets are identical. A WIFA with size n of the input and output alphabet is denoted by an n-WIFA. We prove that for any n > 1, there exists an n-WIFA with delay 2 which cannot be decomposed into two n-WIFAs with delay 1. A one-element logic memory cell is a special WIFA with delay 1, and it is called a delay unit. We show that for any prime number p, every strongly connected p-WIFA with delay 1 can be decomposed into a WIFA with delay 0 and a delay unit, and that any 2-WIFA can be decomposed into a WIFA wiht delay 0 and a sequence of k delay units if and only if every state of the 2-WIFA has delay k.

We propose two lockout-free (starvation-free) mutual exclusion algorithms for the asynchronous multi-writer/reader shared memory model. The first algorithm is a modification of the well-known tournament algorithm for the mutual exclusion problem. By the modification we can speed up the original algorithm. The running time of the modified algorithm from the entrance of the trying region to the entrance of the critical region is at most (n-1)c+O(nl), where n is the number of processes, l is an upper bound on the time between successive two steps of each process, and c is is an upper bound on the time that any user spends in the critical region. The second algorithm is a further modification of the first algorithm. It is designed so that some processes have an advantage of access to the resource over other processes.

Group mutual exclusion is an interesting generalization of the mutual exclusion problem. This problem was introduced by Joung, and some algorithms for the problem have been proposed by incorporating mutual exclusion algorithms. Group mutual exclusion occurs naturally in a situation where a resource can be shared by processes of the same group, but not by processes of a different group. It is also called the congenial talking philosophers problem. In this paper we propose two algorithms based on ticket orders for the group mutual exclusion problem on the asynchronous shared memory model. These algorithms are some modifications of the Bakery algorithm. They satisfy lockout freedom and a high degree of concurrency performance. Each of these algorithms uses single-writer shared variables together with two multi-writer shared variables that are never concurrently written. One of these algorithms has another desirable property, called smooth admission. By this property, during the period that the resource is occupied by the leader (called the chair), a process wishing to join the same group as the leader's group can be granted use of the resource in constant time.

A fast algorithm for computing the maximum number of prime implicants of n-variable symmetric Boolean function is described. A dynamic programming technique is used in the algorithm. The total logarithmic computing time cost and the total uniform computing time cost by a random access machine are O (n4) and O (n3), respectively. The algorithm can be implemented faster by a parallel computer. The corresponding computing time costs by a parallel computer with O (n) processors are O (n3) and O (n2), respectively.

We formulate an improved lower bound on the maximum number of prime implicants of n-variable Boolean functions. It is given as n!/(n/3!(n1)/3!(n2)/3!)(n, 0, (n1)/32)(n, O, (n2)/32), where (n, 0, r) is evaluated by the following recursive procedure: (n, 0, r)0 for r0, (n, 0, 0)1 and (n, 0, r)n!/(r/2!(nr)!(r1)/2!)(n, 0, (r1)/2 2) for 1rn. The total logarithm computing time cost and the total uniform computing time cost of this lower bound by a random access machine are O (n (log2n)2) and O (n), respectively. The ratio of this new lower bound to the old lower bound is bounded by 1c (1/2)n/3, where c is a constant independent of n.

In this paper we discuss some combinatorial problems related to the permutation network devised by Waksman et al. NUM(π) means the number of configurations of the permutation network producing a permutation π. The main result in this paper is that 23N-5-(log2N(log2N+1))/2 is a lower bound on the number of elements in the set {ππ is a permutation on {1, , N} and NUM(π)1}. This is a remarkable improvement on the previous best lower bound 22N-3+(log2N(log2N-3))/2 given by Opferman and Tsao-Wu.

Let T1, , Tn be n spanning trees rooted at node r of graph G. If for any node v, n paths from r to v, each path in each spanning tree of T1, , Tn, are internally disjoint, then T1, , Tn are said to be independent spanning trees rooted at r. A graph G is called an n-channel graph if G has n independent spanning trees rooted at each node of G. We generalize the definition of n-channel graphs. If for any node v of G, among the n paths from r to v, each path in each spanning tree of T1, , Tn, there are k internally disjoint paths, then T1, , Tn are said to be (k,n)-independent spanning trees rooted at r of G. A graph G is called a (k,n)-channel graph if G has (k,n)-independent spanning trees rooted at each node of G. We study two fault-tolerant communication tasks in (k,n)-channel graphs. The first task is reliable broadcasting. We analyze the relation between the reliability and the efficiency of broadcasting in (k,n)-channel graphs. The second task is secure message distribution such that one node called the distributor attempts to send different messages safely to different nodes. We should keep each message secret from the nodes called adversaries. We give two message distribution schemes in (k,n)-channel graphs. The first scheme uses secret sharing, and it can tolerate up to t+k-n listening adversaries for any t < n if G is a (k,n)-channel graph. The second scheme uses unverifiable secret sharing, and it can tolerate up to t+k-n disrupting adversaries for any t < n/3 if G is a (k,n)-channel graph.

We discuss time lower bounds for iterative merge sorts and iterative psueudo-merge sorts on an nn meshconnected processor array. They are 4.5n-3log2n-2 steps and 3.5n-log2n-3 steps for sorting n2 items. We also discuss time lower bounds for these sorting algorithms on higher dimensional models. For the case of the three-dimensional mesh-connected model, 7.25n-4log2n-8 steps and 5.25n-log2n-6 steps are lower bounds for sorting n3 items by iterative merge sorts and iterative pseudo-merge sorts, respectively.

In this paper we analyze the reliability of a simple broadcasting scheme for hypercubes (HCCAST) with random faults. We prove that HCCAST (n) (HCCAST for the n-dimensional hypercube) can tolerate Θ(2n/n) random faulty nodes with a very high probability although it can tolerate only n - 1 faulty nodes in the worst case. By showing that most of the f-fault configurations of the n dimensional hypercube cannot make HCCAST (n) fail unless f is too large, we illustrate that hypercubes are inherently strong enough for tolerating random faults. For a realistic n, the reliability of HCCAST (n) is much better than that of the broadcasting algorithm described in [6] although the latter can asymptotically tolerate faulty links of a constant fraction of all the links. Finally, we compare the fault-tolerant performance of the two broadcasting schemes for n = 15, 16, 17, 18, 19, 20, and we find that for those practical valuse, HCCAST (n) is very reliable.

Two fast parallel sorting algorithms on a mesh-connected model are described. These algorithms are some combinations of row and column sorts, and use just the compare-exchange as their basic operation. The computing time of the first algorithm for sorting n2 items is 6.5n+2 log n-5 steps and the computing time of the second one is not more than 5.5n+0.5 log n+0.5 +1.5 log n-3 steps. The control structures of these algorithms are particularly simple. The correctness of the algorithms are proved in a lucid way by using a function POTENTIAL. The function evaluates the exact number of steps to sort items by parallel bubble sort.

Let R1, , Rn be 3-dimensional iso-oriented objects. We formulate the contour of F=R1Rn, and describe an algorithm for finding the contour. Its computing time and space requirement are O(nlog2n+plogn) and O(n+p) respectively, where p is the number of intersecting pairs of the objects.

A graph G = (V, E) with N nodes is called an N-hyper-ring if V = {0, ..., N-1} and E = {(u, v)(u-v) modulo N is power of 2}. We study embeddings of the 2n-hyper-ring in the n-dimensional hypercube. We first show a greedy embedding with dilation 2 and congestion n+1. We next modify the greedy embedding, and then we obtain an embedding with dilation 4 and congestion 6.