/ 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:
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
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, {\it 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. The works in formal language theory focus on homomorphic characterization, Dyck reduction, 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.
The members of this laboratory give lectures in discrete mathematics, geometry, algorithms and data structures, programming languages, language processing systems, and guide student extracurricular projects (SCCP). Currently, there are seven SCCP projects in this laboratory:
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
Let $ {\cal L} $ be any class of languages, $ {\cal L'} $ be a class of languages which is closed under $ \lambda $ -free homomorphisms. If for any language $ L \in {\cal L} $ over an alphabet $ \Sigma $, there exist an alphabet of k pairs of matching parentheses $ X_k $, Dyck reduction over $ X_k $ and a language $ L_1 \in {\cal L'} $ over $ \Sigma \cup X_k $ such that $ L = {\it Red }(L_1) \cap \sigma^* $, then for any language $ L \in {\cal L} $, there exsist an alphabet $ \Gamma (\supseteq \Sigma) $, a homomorphism $ h: \Gamma^* \rightarrow \Sigma^* $, a Dyck language $ D $ over $ \Gamma $ , and $ L_2 \in {\cal L'} $ such that $ L = h(D \cap L_2) $.
Consider a hypercube regarded as a directed graph, with one edge in each direction between each pair of adjacent nodes. We show that any permutation on the hypercube can be partitioned into two partial permutations of the same size so that each of them can be routed by edge-disjoint directed paths. This result implies that the hypercube can be made rearrangeable by virtually duplicating each edge through time-sharing (or through the use of two wavelengths in the case of optical connection), rather than by physically adding edges as in previous approaches. When our goal is to route as many source-destination pairs of the given permutation as possible by edge-disjoint paths, our result gives a 2-approximate solution which improves previous ones.
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. In cluster fault tolerant routing (abbreviated as CFT routing), we are interested in the number of faulty clusters and the size of the clusters that an interconnection network can tolerate for certain routing problems. As a case study, we investigate the following $k$-pairwise CFT routing in $n$-dimensional hypercubes $H_n$: Given a set of faulty clusters and $k$ distinct non-faulty node pairs $(s_1,t_1),...,(s_k,t_k)$ in $H_n$, find $k$ fault-free node-disjoint paths $s_i\rightarrow t_i$, $1\leq i\leq k$. We show that $H_n$ can tolerate $n-2$ faulty clusters of diameter 1 plus one faulty node for the $k$-pairwise CFT routing with $k=1$. For $n\geq 4$ and $2\leq k\leq \lceil n/2\rceil$, we prove that $H_n$ can tolerate $n-2k+1$ faulty clusters of diameter 1 for the $k$-pairwise CFT routing. We also give an $O(kn\log n)$ time algorithm which finds the $k$ paths for the mentioned problem. Our algorithm implies an $O(n^2\log n)$ time algorithm for the $k$-pairwise node-disjoint paths problem in $H_n$, which improves the previous result of $O(n^3\log n)$.
In this paper, we give an algorithm which, given at most $n-1$ faulty nodes and non-faulty nodes $s$ and $t$ in the $n$-dimensional hypercube $H_n$, finds a fault-free path $s\rightarrow t$ of length at most $d(s,t)+2$ in $O(n)$ time, where $d(s,t)$ is the distance between $s$ and $t$ in $H_n$. Using this algorithm as a subroutine, we give another algorithm which, given at most $2n-3$ faulty nodes such that the faulty nodes can be covered by $n-1$ subgraphs of diameter 1, finds a fault-free path $s\rightarrow t$ of length at most $d(s,t)+4$ in $O(n)$ time. The algorithms are optimal in the sense that both the upper bounds on the length of $s\rightarrow t$ and the time complexity are optimal.
In this paper, we study the following node-to-node and node-to-set routing problems in $r$-dimensional torus $T^r_n$ with $r\geq 2$ and $n\geq 4$ nodes in each dimension: given at most $2r-1$ faulty nodes and non-faulty nodes $s$ and $t$ in $T^r_n$, find a fault-free path $s\rightarrow t$; and given at most $2r-k$ faulty nodes and non-faulty nodes $s$ and $t_1,\ldots,t_k$ in $T^r_n$, find $k$ fault-free node-disjoint paths $s\rightarrow t_i$, $1\leq i\leq k$. We give an $O(r^2)$ time algorithm which finds a fault-free path $s\rightarrow t$ of length at most $d(T^r_n)+1$ for the node-to-node routing, where $d(T^r_n)$ is the diameter of $T^r_n$. For node-to-set routing, we show an $O(r^3)$ time algorithm which finds $k$ fault-free node-disjoint paths $s\rightarrow t_i$, $1\leq i\leq k$, of length at most $d(T^r_n)+1$. The upper bounds on the length of the found paths are optimal. From this, Rabin diameter of $T^r_n$ is $d(T^r_n)+1$.
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.
Understanding lengthy mathematical proofs requires strong concentration. Authors must efficiently map the whole logical structures into sequential texts. One way to ease such tasks is presenting the logical structure in a functional programming style. In our method, functional proofs are implemented by a real programming language. The behavior of each function appearing in the proofs as a building block is ready to be visualized with concrete data. This paper contains a case study of the well-known Dirichlet's theorem on the convergence of Fourier series. It shows relevance of our method in rigorous mathematical presentations that involve epsilon-delta arguments intensively.
Refereed Proceeding Papers
Given a graph $G$, a cluster $C$ is a connected subgraph of $G$, and $C$ is called faulty cluster if all nodes in $C$ are faulty. Given an $n$-dimensional star graph $G_n$ with $n-2$ faulty clusters of diameter at most 2, it has been shown in \cite{GuM2595x} that any two non-faulty nodes $s$ and $t$ of $G_n$ can be connected by a fault-free path of length at most $d(G_n)+6$ for $n\neq 4,~$ and $d(G_n)+7$ otherwise in $O(n^2)$ time, where $d(G_n)=\lfloor \frac{3(n-1)}{2}\rfloor$ is the diameter of $G_n$. In this paper, we introduce the concept of 3-separated paths and show that a fault-free path $s\rightarrow t$ of length at $d(G_n)+2$ can be found in $O(n^2)$ time.
In this paper, we give efficient parallel and distributed algorithms for the topological sort problem on acyclic graphs with $n$ vertices. Our parallel algorithm solves the problem on a CREW PRAM in $O(\log^2 n)$ time with $O(M(n)/\log n)$ processors, where $M(n)$ denotes the number of processors needed to multiply two $n\times n$ integer matrices over the integer ring. The best known upper bound of $M(n)$ is $O(n^{2.376})$. The parallel algorithm can also solve the problem on processor arrays with reconfigurable bus systems in $O(1)$ time and $O(n^3)$ processors. Our distributed algorithm solves the topological sort problem of an arbitrary asynchronous network with communication complexity $O(n^2)$.
A parallel algorithm to find $k$ ,2 $\leq k \leq n^{n-2}$ spanning trees from a connected, weighted and undirected graph G(V,E,W) in the order of increasing weight is presented. It runs in O(T(n)+ klogn) time with O($n^2$/logn) processors on a CERW PRAM, where n=$|V|$, m = $|E|$ and T(n), O(logn) $\leq$ T(n) $\leq$ O($log^2n$), is the time of the fastest parallel algorithms to find a minimum spanning tree of G on a CREW PRAM with no more than O($n^2$/logn) processors. Since T(n) = O($log^2n$) for the time being, this result shows that to find k minimum spanning trees can be done in the same time bound as to find just one when k $\leq$ O(logn) on a CREW PRAM.
Recently, a new approach to analyze genomes evolving was proposed which is based on comparison of gene orders versus traditional comparison of DNA sequences (Sankoff et al, 1992). The approach is based on the global rearrangements (e.g., inversions and transpositions of fragments). Analysis of genomes evolving by inversions and transpositions leads to a combinatorial problem of sorting by reversals and transpositions, i.e., sorting of a permutation using reversals and transpositions of arbitrary fragments. %The problem is conjectured as NP-hard. We study sorting of signed permutations by reversals and transpositions, a problem which adequately models genome rearrangements, as the genes in DNA are oriented. We establish a lower bound and give a 2-approximation algorithm for the problem.
Consider the following node-to-set routing problem in the $n$-dimensional star graph $G_n$: given a node $s$ and a set of nodes $T=\{t_1,\ldots,t_k\}$, $2\leq k\leq n-1$, find $k$ node-disjoint paths $s\rightarrow t_i$, $1\leq i\leq k$. From Menger's theorem, it is known that $G_n$ can tolerate at most $(n-1)-k$ arbitrary faulty nodes for node-to-set routing problem. In this paper, we prove that $G_n$ can tolerate as many as $(n-1)-k$ arbitrary faulty clusters of diameter at most 2, where the faulty cluster is a connected subgraph of $G_n$ such that all its nodes are faulty. This result implies that $G_n$ can tolerate as many as $n(n-1-k)$ faulty nodes for node-to-set routing if the faulty nodes can be covered by $(n-1)-k$ subgraphs of diameter at most 2. We also show an algorithm which, in the presence of up to $(n-1)-k$ faulty clusters of diameter at most 2, finds the $k$ routing paths of length at most $d(G_n)+9$ for node-to-set routing in $O(|F|+kn)$ time, where $d(G_n)=\lfloor \frac{3(n-1)}{2}\rfloor$ is the diameter of $G_n$ and $|F|$ is the total number of faulty nodes in faulty clusters.
In this paper, we consider the fault tolerant broadcasting problem in hypercube/star-graph connected multi-port, MIMD multiprocessor systems in which each processor can send message to all its neighbors at a single time step. We give efficient broadcasting algorithms in the faulty hypercube and star graph when each node has at least one fault-free neighbor and the global faulty information is known. Our algorithm for the $n$-dimensional hypercube $H_n$, given a set $F$ with $|F|\leq 2n-3$ of faulty nodes in $H_n$, completes the broadcasting in at most $n+2$ time steps and $2^n-|F|$ traffic steps. The algorithm is optimal in both time steps and traffic steps. Our algorithm for the $n$-dimensional star graph $G_n$, given $|F|\leq 2n-5$, completes the broadcasting in $d(G_n)+c$ time steps and $n!+O(n)$ traffic steps, where $d(G_n)=\lfloor\frac{3(n-1)}{2}\rfloor$ is the diameter of $G_n$ and $c$ is a constant.
In this paper, we give an algorithm which, given at most $2n-3$ arbitrary faulty nodes and non-faulty nodes $s$ and $t$ such that $s$ and $t$ are not isolated in the $n$-dimensional hypercube $H_n$, finds a fault-free path $s\rightarrow t$ of length at most $d(s,t)+4$ for $d(s,t)\leq n-2$, of length at most $d(s,t)+2$ for $d(s,t)=n-1$, and of length $d(s,t)$ for $d(s,t)=n$, where $d(s,t)$ is the distance between $s$ and $t$. The length of paths of our algorithm is optimal. The algorithm finds the path in optimal $O(n)$ time which improves the previous one of $O(n\log n)$.
Books
Grants
Academic Activities
Others