Next: Mathematical Foundation of Up: Department of Computer Previous: Department of Computer

# Foundation of Computer Science Laboratory

/ Satoshi Okawa / Professor
/ Qian Ping Gu / Associate Professor
/ Shuichi Yukita / Associate Professor

The research and education activities in this laboratory focus on the theoretical foundations of computers and computations. In particular, our work covers the following areas.

• Algorithms and computational complexity;
• Programming languages; and
• Discrete Mathematics.
The research in this laboratory is divided into two parts. The first part consists of the work that follows the research in the above areas. The goal of this research is to provide the theoretical foundations for the education and research activities in this university.

The second part of our work is the creative research in some specific areas of the theoretical foundations of computer science. Currently, we are working on

• Parallel computation;
• Computational learning theory; and
• Dynamical systems in discrete mathematics.
The recent impressive advances in VLSI and fiber optics technologies have made it possible to design and build high-performance parallel computers and computer networks. Research in parallel computation has become one of the most important areas in computer science and is accelerating at a rapid pace. We have been working in several principle areas of parallel computation such as, node fault tolerant routing in interconnection networks, sorting and routing in meshes, and so on.

Machine learning is another major area that we are interested in. Our focuses are on computational learning theory and its relationship with empirical machine learning conducted in the field of artificial intelligence. The works in dynamical systems in discrete mathematics include Tessellation automata theory, algebra structures of interconnection networks, and so on. Many of our works have been published/accepted by leading international journals and conferences.

The research activities in this laboratory are based on the free work of each faulty member. Faculty members exchange their ideas and results through regular seminars and free discussions to work on common global areas.

Several leading experts in the world were invited to give talks in several areas of computer science last year. These talks have greatly stimulated and brought fresh air to the work here. Joint researchs with other laboratories and other universities/institutions have been actively conducted as well. This laboratory gave many contributions to the First Aizu International Symposium on Parallel Algorithms/Architecture Synthesis (pAs'95).

The members of this laboratory give lectures in discrete mathematics, geometry, algorithms and data structures, programming languages, and guide student extracurricular projects (SCCP). Currently, there are four SCCP projects in this laboratory:

• The Route Guidance System---An Introduction to Graph Theory and Its Applications, supervised by Prof. Okawa.
• Concrete Mathematics, supervised by Prof. Yukita.
• PC-UNIX and Networking, supervised by Prof. Yukita.
• Parallel Algorithms and Data Structures, supervised by Prof. Gu.
Developing coursewares is another important teaching activity of this laboratory. Coursewares have been developed in the areas, Vector Calculus, Fourier Analysis and Mathematics for CG. All of them feature top-down approaches and self-learning by computers. In the middle/long term plan, we will develop more coursewares in parallel computation, machine learning, discrete mathematics, and so on, based on our research works.

Refereed Journal Papers

1. Gu, J. and Gu, Q. and Du, Z. Convergence properties of optimization algorithms for the SAT problem. In IEEE Trans. on Computers, 1994, accepted,

The satisfiability (SAT) problem is a basic problem in computing theory. Presently, an active area of research on SAT problem is to design efficient algorithms for verifying the satisfiability of a {\it CNF} Boolean formula, i.e., finding a solution for a satisfiable {\it CNF} formula. A new formulation, the {\it Universal SAT} problem model, which transforms the SAT problem on Boolean space into an optimization problem on real space has been developed. In this paper, we prove the convergence ratios of three basic optimization methods for the {\it Universal SAT} problem. We show that, subject to certain conditions, the steepest descent method has a linear convergence ratio $\beta<1$, Newton's method has a convergence ratio of order two, and the convergence ratio of the coordinate descent method is approximately $(1-\beta/m)$ for the {\it Universal SAT} problem with $m$ variables. An algorithm based on the coordinate descent method for the {\it Universal SAT} problem is also presented in this paper. Experimental results show that this algorithm is more efficient than the previous ones in finding a solution for certain classes of $CNF$ Boolean formulae.

2. Gu, Q. and Gu, J. Two packet routing algorithms on a mesh-connected computer. In IEEE Trans. on Parallel and Distributed Systems, 1995, Vol.6, No.4, p:436-440.

In this paper, we give two algorithms for the 1-1 routing problems on a mesh-connected computer. The first algorithm, with queue size 28, solves the 1-1 routing problem on an $n\times n$ mesh-connected computer in $2n+O(1)$ steps. This improves the previous queue size $75$. The second algorithm solves the 1-1 routing problem in $2n-2$ steps with queue size $12t_s/s$, where $t_s$ is the time for sorting an $s\times s$ mesh into a row major order for all $s\geq 1$. This result improves the previous queue size $18.67t_s/s$.

Refereed Proceeding Papers

1. Gu, Q. and Peng, S. Node-to-node cluster fault tolerant routing in star networks. In Proc. of 1995 Joint Symposium on Parallel Processing, JSPP'95. February, 1995. to appear.

In this paper, we study node-to-node fault tolerant routing problem in $n$-dimensional star graphs $G_n$ based on the cluster fault tolerant model which is a natural extension of the well studied node fault tolerant model. For a graph $G$, a cluster $C$ is a connected subgraph of $G$, and $C$ is called fault cluster if all nodes in $C$ are faulty. In cluster fault tolerant routing, the number of fault clusters and the size of the fault clusters that can be tolerated are studied. For node-to-node fault tolerant routing problem in $G_n$, we prove that $G_n$ can tolerate as many as $n-2$ arbitrary fault clusters of diameter at most 2. This result shows that star graphs $G_n$ can tolerate as many as $n(n-2)\approx (\log N/\log\log N)^2$ fault nodes, where $N=n!$ is the number of nodes in $G_n$, if the fault nodes can be partitioned into clusters. We also give an $O(n^2)$ optimal time algorithm which finds a fault-free routing path of length at most $d(G_n)+7$ for node-to-node cluster fault tolerant routing problem in $G_n$, where $d(G_n)=\lfloor \frac{3(n-1)}{2}\rfloor$ is the diameter of $G_n$.

2. Gu, Q. and Peng, S. Fault tolerant routing in toroidal networks. In Proc. of the First Aizu International Symposium on Parallel Algorithm/Architecture Sythesis, pAs'95. March, 1995, p162-168. IEEE Computer Society Press.

In this paper, we give an $O(r^2)$ time algorithm for constructing a fault-free routing path of optimal length between any two non-fault nodes of a $r$-dimensional torus with $2r-1$ faulty nodes. %The fastest previously known algorithm for this problem takes $O(r^3)$ time; We show that Rabin diameter of a $r$-dimensional torus is its diameter plus one. We also describe a cluster fault tolerant (CFT) routing model and give an efficient algorithm for node-to-node CFT routing.

3. Gu, Q. and Peng, S. Algorithms for node disjoint paths in incomplete star networks. In Proc. of 1994 International Conference on Parallel and Distributed Systems, ICPAD'94. December, 1994, p296-303. IEEE Computer Society Press.

We give efficient algorithms for node disjoint path problems in incomplete star graphs which are defined in this paper to reduce the large gaps in the size of systems based on star graph topologies. Four disjoint path paradigms in incomplete star graphs are discussed: (1) disjoint paths between a pair of nodes $s$ and $t$, (2) disjoint paths from a node $s$ to a set $T$ of nodes, (3) disjoint paths from a set $S$ of nodes to a set $T$ of nodes, and (4) disjoint paths between node pairs $(s_i,t_i)$. We give algorithms which can find the maximum number of disjoint paths for these paradigms in optimal time. For an $n$-dimensional incomplete star graph $G_{n,m}$, the length of the disjoint paths constructed by our algorithms is at most $d(G_{n,m})+c$, where $d(G_{n,m})$ is the diameter of $G_{n,m}$ and $c$ is a small constant. This paper also shows that wide-diameter $d^W_{n-2}(G_{n,m})$, Rabin-diameter $d^R_{n-2}(G_{n,m})$, set-diameter $d^S_{n-2}(G_{n,m})$, and pair-diameter $d^P_{\lceil\frac{n-2}{2}\rceil}(G_{n,m})$ of $G_{n,m}$ are at most $d(G_{n,m})+c$.

4. Gu, Q. and Peng, S. Advanced fault tolerant routing in hypercubes. In Proc. of the International Symposium on Parallel Architectures, Algorithms, and Networks, ISPAN'94. December, 1994, p189-196, IEEE Computer Society Press,

In this paper, we study the fault tolerant properties of $n$-dimensional hypercubes $H_n$ for node-to-set and set-to-set routing problems on a new model, cluster fault tolerant routing, which is a natural extension of the well studied node fault tolerant routing. A cluster of a graph $G$ is a connected subgraph of $G$ and a cluster is called faulty if all nodes in the cluster are faulty. For node-to-set routing and set-to-set routing, where $k$ ($2\leq k\leq n$) fault-free node disjoint paths are needed, in $H_n$, we show that the maximum numbers of faulty clusters of diameter at most 1 that can be tolerated is $n-k$. We give an $O(kn)$ optimal time algorithm which finds $k$ fault-free node disjoint paths of length at most $n+3$ for node-to-set cluster fault tolerant routing in $H_n$. The upper bound $n+2$ on the length of the paths for node-to-set routing in $H_n$ is optimal. For set-to-set cluster fault tolerant routing in $H_n$, we give an $O(kn\log k)$ time algorithm which finds $k$ fault-free node disjoint paths of length at most $2n$.

5. Gu, Q. and Peng, S. $k$-Pairwise cluster fault tolerant routing in hypercubes. In Proc. of the 5th International Symposium on Algorithms and Computation, ISAAC'94. August, 1994, p342-350, Springer-Verlag,

In this paper, we introduce a general fault-tolerant routing problem, cluster fault tolerant routing, which is a natural extension of the well studied node fault tolerant routing problem. A cluster is a connected subgraph of a graph $G$ and a cluster is faulty if all nodes in it are faulty. Cluster fault tolerant (abbreviated as CFT in what follows) routing studies the number of faulty clusters and the size (diameter) of the clusters that an interconnection network can tolerate in fault tolerant routing problems. In this paper, we investigate $k$-pairwise CFT routing in an $n$-dimensional hypercubes $H_n$. We give an $O(n^2\log n)$ time algorithm which finds the required routing paths for $k$-pairwise CFT routing in $H_n$. Our algorithm implies an $O(n^2\log n)$ algorithm for $k$-pairwise node disjoint path problem in $H_n$. The algorithm for $k$-pairwise node disjoint path problem in $H_n$ significantly improves the previous results of time complexity $O(n^3\log n)$. As an extension of the fault diameter which is studied in node fault tolerant routing, we define cluster fault diameter for interconnection networks. We prove that the cluster fault diameter of $H_n$ is $n+2$ when the diameters of the faulty clusters are at most $1$. We also show an $O(n)$ time algorithm which finds a path of length at most $n+3$ for node-to-node CFT routing ($k$-pairwise CFT routing with $k=1$) in $H_n$.

6. Gu, J. and Gu, Q. Average time complexity of the SAT1.2 algorithm. In Proc. of the 5th International Symposium on Algorithms and Computation, ISAAC'94 August, 1994, p146-154, Springer-Verlag.

The satisfiability (SAT) problem is a basic problem in computing theory and artificial intelligence. In this paper, we describe and analyze the average time complexity of a local search algorithm, the $SAT1.2$ algorithm, for the SAT problem. For the randomly generated $CNF$ formulae with $n$ clauses, $m$ variables, and $l$ literals in each clause, the average run time of the $SAT1.2$ algorithm is $O(m^{O(1)}n^2)$ for $l\geq 3$ and $n/m\leq \alpha 2^l/l$, where $\alpha 7. Gu, Q. and Peng, S. Efficient algorithms for disjoint paths in star networks. In Proc. of the 6th International Transputer/Occam Conference. June, 1994, p53-65, IOS Press. In this paper, we give optimal time algorithms for the following node disjoint path problems in$n$-dimensional star graphs$G_n$: (1) Given an arbitrary node$s$and a set of arbitrary distinct nodes$T=\{t_1,\ldots,t_{n-1}\}$,$s\not\in T$, in$G_n$, find$n-1$node disjoint paths connecting$s$and each node of$T$; and (2) Given arbitrary$k= \lceil \frac{n-1}{2}\rceil$pairs of distinct nodes$(s_1,t_1),\ldots,(s_k,t_k)$in$G_n$, find$k$node disjoint paths, one path connecting one pair of nodes. For problem (1), our algorithm finds the$n-1$node disjoint paths of length at most$d(G_n)+4$in$O(n^2)$optimal time, where$d(G_n)=\lfloor\frac{3(n-1)}{2}\rfloor$is the diameter of$G_n$. The length of the paths given in this paper improves the previous result of$5n-2$. For problem (2), our algorithm finds the$k$node disjoint paths of length at most$d(G_n)+5$in$O(n^2)$optimal time. Our results improve the previous ones of the time$O(n^4\log n)$and the length$4(n-2)$, respectively. From the upper bounds on the length of the paths for problems (1) and (2) of this paper, we also get that Rabin-diameter$d^R_{n-1}(G_n)$and$k$-pair-diameter$d^P_{k}(G_n)$of$G_n$satisfy$d^R_{n-1}(G_n)\leq d(G_n)+4$and$d^P_k(G_n)\leq d(G_n)+5$, respectively, where$k=\lceil\frac{n-1}{2}\rceil$. 8. Gu, Q. and Takaoka, T. A parallel algorithm for the longest path problem on acyclic graphs with integer arc lengths. In Proc. of the 6th International Transputer/Occam Conference. June, 1994, p66-75, IOS Press. This paper presents a parallel algorithm that computes the single source longest path problem on acyclic graphs$G(V,A)$with integer arc lengths on SIMD-SM-EREW parallel computers. The algorithm solves the problem in$O(\log^2(ln))$time,$O((ln)^{2.376})$processors, and$O((ln)^2)$memory space, where$n=|V|$and the arc lengths are integers in the set$\{1,2,\ldots,l\}$. For any constant$l$, our algorithm solves the single source longest path problem in$O(\log^2n)$time,$O(n^{2.376})$processors, and$O(n^2)$memory space. Our algorithm is then used to derive$O(\log^2n)$time,$O(n^{2.376})$processors, and$O(n^2)$memory space parallel algorithms for a number of problems, such as minimum coloring, maximum clique, and so on, of permutation graphs on an SIMD-SM-EREW computer. 9. Gu, Q. and Okawa, S. and Peng, S. Disjoint paths in hypercubes and star graphs. In Proc. of 1994 Joint Symposium on Parallel Processing, JSPP'94. May, 1994, p49-56. The set-to-set routing which allows certain node failure is considered. We first present an interesting theorem for the set-to-set routing problem in general graphs. Then, efficient algorithms are given for the set-to-set routing problem in hypercubes and star graphs. Hypercubes and star graphs have been accepted as attractive interconnection networks. They have logarithmic and sublogarithmic node degree and diameter, respectively. They both possess rich structure and symmetry properties as well as many desirable fault tolerance characteristics. For set-to-set routing in$n$-dimensional hypercubes$H_n$our algorithm finds the routing paths of length at most$2n$in$O(n^2\log n)$time. For set-to-set routing in$n$dimensional star graphs$G_n$, our algorithm finds the routing paths of length at most$\lfloor \frac{3(n-1)}{2} \rfloor + 5$in$O(n^2)$optimal time. Unrefereed Papers 1. Gu, Q. and Okawa, S. and Peng, S. Efficient algorithms for node disjoint path problems. In Proc. of 1994 IEICE Fall Conference. September, 1994. p SD-I. Technical Reports 1. Gu, Q. and Peng, S. An efficient algorithm for$k$-pairwise node disjoint path problem in hypercubes. Technical Report of IEICE. March, 1995. No. COMP94-109. In this paper, we give an efficient algorithm for the following$k$-pairwise node disjoint path problem in$n$-dimensional hypercubes$H_n$: Given$k=\lceil \frac{n}{2}\rceil$pairs of$2k$distinct nodes$(s_1,t_1),\ldots,(s_k,t_k)$in$H_n$,$n\geq 4$, find$k$node disjoint paths, each path connecting one pair of nodes. Our algorithm finds the$k$node disjoint paths in$O(n^2\log^* n)$time which improves the previous result of$O(n^2\log n)$. The length of the paths constructed in our algorithm is at most$n+\lceil \log n\rceil +1$which improves the previous result of$2n$as well. The result of this paper shows that the$k$-pair-diameter %and$k$-set-diameter of$H_n$satisfy$d^P_{\lceil\frac{n}{2}\rceil}(H_n)$of$H_n$satisfies$d^P_{\lceil\frac{n}{2}\rceil}(H_n)\leq n+\lceil\log n\rceil+1$. 2. Gu, Q. and Peng, S.$k$-pairwise cluster fault tolerant routing in star graphs. Technical Report of The University of Aizu, No. 95-1-002, February, 1995. 3. Gu, Q. and Peng, S. Cluster fault tolerant routing in star graphs. Technical Report of IEICE, No. COMP94-49 October, 1994. 4. Gu, Q. and Peng, S. Fault tolerant routing in toroidal networks. Technical Report of IEICE, No. COMP94-43, September, 1994. 5. Gu, Q. and Peng, S.$k\$-pairwise cluster fault tolerant routing in hypercubes. Technical Report of IEICE, No. COMP94-42, September, 1994.

6. Gu, Q. and Peng, S. Linear time algorithms for fault tolerant routing in hypercubes and star graphs. Technical Report of The University of Aizu, No. 94-1-039, August, 1994.

7. Yukita, S. Tessellation automata of free groups. Technical Report of The University of Aizu, No. 94-1-044, October, 1994.

8. Yukita, S. Tessellation automata of Fuchsian groups. Technical Report of The University of Aizu, No. 94-1-045, October, 1994.

9. Yukita, S. Functional Presentation of Fourier Series Convergence. Technical Report of The University of Aizu, No. 95-1-011, March, 1995.

1. Satoshi Okawa. Reviewer of the Information Processing Letters. 1994.

2. Satoshi Okawa. Reviewer of IEICE Transactions on Information and Systems 1994.

3. Satoshi Okawa. Reviewer of IEICE Transactions A and D-I (Japanese) 1994.

4. Satoshi Okawa. Reviewer of Interdisciplinary Information Sciences, GSIS, Tohoku University, 1994.

5. Satoshi Okawa. Programm Committee member of the First Aizu International Symposium on Parallel Algorithm/Architecture Synthesis, pAs'95, March 1995.

6. Satoshi Okawa. Session Chair of the First Aizu International Symposium on Parallel Algorithm/Architecture Synthesis, pAs'95, March 1995.

7. Qian Ping Gu. Editor of the Proceedings of the First Aizu International Symposium on Parallel Algorithm/Architecture Synthesis, pAs'95, March 1995.

8. Qian Ping Gu. Programm Committee member of the First Aizu International Symposium on Parallel Algorithm/Architecture Synthesis, pAs'95, March 1995.

9. Qian Ping Gu. Session Chair of the First Aizu International Symposium on Parallel Algorithm/Architecture Synthesis, pAs'95, March 1995.

10. Qian Ping Gu. Reviewer for IEEE Trans. on Parallel and Distributed Systems, Journal of Parallel and Distributed Computing, and Parallel Computing.

Next: Mathematical Foundation of Up: Department of Computer Previous: Department of Computer

www@u-aizu.ac.jp
January 1996