/ 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 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
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 four SCCP projects in this laboratory:
The graph theory provides good examples to make student understand how abstract theories work well in resolving practical problems. We study the graph theory through considering problems we meet in constructing a route guidance system.
The project aims at developing students' skills in experimental mathematics making full use of computers. With these skills, we will investigate unsolved mathematical problems. We also reformulate theoretically solved problems in algorithmic manner. In other words, we "implement" the solutions to the already solved problems.
The project begins with the installation of UNIX on PC's. We experiment various network configurations, through which we gain deep understandings of how network protocols work.
In this project, we have a comprehensive study in algorithms and data structures based on both sequential and parallel computation models.
Refereed Journal Papers
We give a direct proof of the result of Latteux and Turakainen that the full class of recursively enumerable languages can be obtained from minimal linear languages (which are generated by linear context-free grammars with only one nonterminal symbol) by Dyck reductions (which reduce pairs of parentheses to the empty word).
In this paper, we give an algorithm which, given a set $F$ of at most $n-k$ faulty nodes, and two sets $S=\{s_1,\ldots,s_k\}$ and $T=\{t_1,\ldots,t_k\}$, $1\leq k\leq n$, of non-faulty nodes in $n$-dimensional hypercubes $H_n$, finds $k$ fault-free node disjoint paths $s_i\rightarrow t_{j_i}$, where $(j_1,\ldots,j_k)$ is a permutation of $(1,\ldots,k)$, of length at most $n+k$ in $O(kn\log k)$ time. The result of this paper implies that $n$ disjoint paths of length at most $2n$ for set-to-set node disjoint path problem in $H_n$ can be found in $O(n^2\log n)$ time.
In this paper, we study node-to-node fault tolerant routing problem in $n$-dimensional hypercubes $H_n$ based on the cluster fault tolerant model. For a graph $G$, a fault cluster is a connected subgraph of $G$ such that all its nodes are faulty. In cluster fault tolerant routing problems, how many fault clusters and how large of those clusters can be tolerated are studied. It was proved that for node-to-node routing, $H_n$ can tolerate as many as $n-1$ fault clusters of diameter at most 1 with at most $2n-3$ fault nodes in total. In this paper, we give an algorithm which, given at most $n-1$ fault clusters of diameter at most 1 with $2n-3$ fault nodes in total and non-fault nodes $s$ and $t$ in $H_n$, finds a fault-free path $s\rightarrow t$ of length at most $n+2$ in $O(n)$ time. The upper bounds on the time complexity of the algorithm and the length of the fault-free path in this paper are optimal.
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 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. Many optimization techniques, such as the steepest descent method, Newton's method, and the coordinate descent method, can be used to solve the {\it Universal SAT} problem. In this paper, we prove that, %subject to certain conditions, when the initial solution is sufficiently close to the optimal solution, 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 steepest 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 satisfiable $CNF$ Boolean formulas.
This paper defines a new fault tolerant routing model, {\em cluster fault tolerant routing}, and gives the solutions for node-to-node cluster fault tolerant routing in star graphs.
In this paper, we study the following node-to-node fault tolerant routing problem: In the presence of up to $n-1$ faulty nodes, find a fault-free path which connects any two non-faulty nodes $s$ and $t$ in an $n$-connected graph. For node-to-node fault tolerant routing in $n$-dimensional hypercubes $H_n$, we give an algorithm which finds a fault-free path $s\rightarrow t$ of length at most $d(s,t)+2\lceil\log \frac{n}{d(s,t)}\rceil$ in $O(n)$ time, where $d(s,t)$ is the distance between $s$ and $t$. We also show that a fault-free path $s\rightarrow t$ in $H_n$ of length at most $d(s,t)+2i$, $1\leq i< \lceil\log \frac{n}{d(s,t)}\rceil$, can be found in $O(d(s,t)\frac{n}{2^{i-1}}+n)$ time. For node-to-node fault tolerant routing in $n$-dimensional star graphs $G_n$, we give an algorithm which finds a fault-free path $s\rightarrow t$ of length at most $\min\{d(G_n)+3,d(s,t)+6\}$ in $O(n)$ time, where $d(G_n)=\lfloor \frac{3(n-1)}{2}\rfloor$ is the diameter of $G_n$. It is previously known that, in $H_n$, a fault-free path $s\rightarrow t$ of length at most $d(s,t)$ for $d(s,t)=n$ and at most $d(s,t)+2$ for $d(s,t)< n$ can be found in $O(d(s,t)n)$ time, and in $G_n$, a fault-free path $s\rightarrow t$ of length at most $\min\{d(G_n)+1,d(s,t)+4\}$ can be found in $O(d(s,t)n)$ time. When the time efficiency of finding the routing path is more important than the length of the path, the algorithms in this paper are better than the previous ones.
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.
In this paper, we give an algorithm which, given a set $F$ of at most $(n-1)-k$ faulty nodes, and two sets $S=\{s_1,\ldots,s_k\}$ and $T=\{t_1,\ldots,t_k\}$, $1\leq k\leq n-1$, of non-faulty nodes in $n$-dimensional star graphs $G_n$, finds $k$ fault-free node disjoint paths $s_i\rightarrow t_{j_i}$, where $(j_1,\ldots,j_k)$ is any permutation of $(1,\ldots,k)$, of length at most $d(G_n)+5$ in $O(kn)$ optimal time, where $d(G_n)=\lfloor \frac{3(n-1)}{2} \rfloor $ is the diameter of $G_n$.
Cellular automata on free groups are investigated. Free groups are considered to be the simplest class of examples that model hyperbolic spaces. Two notions of {\em periodicity} and stable periodicityare introduced. With these notions the relations among Period preservability, injectivity and surjectivity of parallel maps are shown to be almost the same as in the case of Euclidean tessellations. We also show the equivalence of Finite orderedness and strong Poisson stability.
Refereed Proceeding Papers
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$.
Given a node $s$ and a set $T=\{t_1,\ldots,t_k\}$ of $k$ nodes in a $k$-connected graph $G$, node-to-set routing is to find $k$ node disjoint paths $P_i: s\rightarrow t_i,~1 \leq i \leq k$. In this paper, we give $O(n^2)$ time algorithms for node-to-set routing in $n$-dimensional star graphs $G_n$ which is $(n-1)$-connected. Our algorithms find $n-1$ node disjoint paths of length at most $d(G_n)+1$ for $n\neq 4,6$ and at most $d(G_n)+2$, otherwise, for node-to-set routing in $G_n$, where $d(G_n)=\lfloor \frac{3(n-1)}{2}\rfloor$ is the diameter of $G_n$. The optimal upper bound on the length of $k$ disjoint paths for node-to-set routing in a $k$-connected graph $G$ is known as {\it Rabin diameter} of $G$. In this paper, we also prove that Rabin diameter of $G_n$ is $d(G_n)+1$ for $n\neq 4,6$ and $d(G_n)+2$, otherwise.
In this paper, we give a linear time algorithm which finds a fault-free routing path of optimal length for node-to-node cluster fault tolerant routing in hypercubes. In cluster fault tolerant routing, the routing problem in a graph $G$ is considered under the situation that a certain number of subgraphs of $G$ failed. A cluster is a connected subgraph of $G$ and a cluster is faulty if all nodes in it are faulty. It was proved that for node-to-node routing, an $n$-dimensional hypercube $H_n$ can tolerate as many as $n-1$ fault clusters of diameter at most 1 with at most $2n-3$ fault nodes in total. Given a tolerable set of fault clusters and two distinct non-fault nodes $s$ and $t$ in $H_n$, it was proved that the optimal upper bound of the length of a fault-free path connecting $s$ and $t$ is $n+2$ and the fault-free path of length at most $n+2$ can be found in $O(n^2)$ time. In this paper, we present an $O(n)$ time algorithm which finds a fault-free path of length at most $n+2$ that connects $s$ and $t$.
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$.
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.
Recently,
Two paths $P$ and $Q$ in a graph $G$ are $d$-separated if for any node $u$ in $P$ and any node $v$ in $Q$ except possibly the common end-nodes, the distance between $u$ and $v$ is at least $d$. In this paper, we study the following node-to-node routing problem in hypercubes: (1) finding 2-separated paths in free space (without obstacles); (2) finding disjoint paths with path-shaped obstacles. We give algorithms to construct the 2-separated/disjoint paths for node-to-node routing problems (1) and (2), and show that the numbers of paths constructed by our algorithms are maximum in the worst case.
Set-to-set node-disjoint paths problem is that given two sets $S=\{s_1,\ldots,s_k\}$ and $T=\{t_1,\ldots,t_k\}$ of nodes in a graph, find $k$ node disjoint paths $s_i\rightarrow t_{j_i}$, where $(j_1,\ldots,j_k)$ is any permutation of $(1,\ldots,k)$. For general undirect graphs $G(V,E)$, this problem is usually solved by applying flow techniques which take Poly($|V|$) time. In this paper, we give an algorithm which, given $S=\{s_1,\ldots,s_k\}$ and $T=\{t_1,\ldots,t_k\}$, $1\leq k\leq n$, in an $n$-dimensional hypercube $H_n$ which has $2^n$ nodes, finds the $k$ disjoint paths $s_i\rightarrow t_{j_i}$ of length at most $n+\log k+2$ in $O(kn\log^* k)$ time. The previous results of the length of the $k$ paths and the run time of finding the $k$ paths in $H_n$ are $n+k$ and $O(kn\log k)$, respectively.
In this paper, we give an algorithm which, given at most $n-1$ arbitrary 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$ for $d(s,t) < n$ and of length $d(s,t)$ for $d(s,t)=n$ in $O(n)$ time, where $d(s,t)$ is the distance between $s$ and $t$. The previous results on the above problem are that (1) Path length: $d(s,t)+2$ for $d(s,t)< n$ and $d(s,t)$ for $d(s,t)=n$. The time complexity: $O(n\log n)$. (2) Path length: $d(s,t)+2\lceil\log\frac{n}{d(s,t)}\rceil$. The time complexity: $O(n)$.\\ We also give an algorithm which, given at most $n-1$ faulty clusters of diameter at most 1 with $2n-3$ faulty nodes in total and non-faulty nodes $s$ and $t$ in $H_n$, finds a fault-free path $s\rightarrow t$ of length at most $d(s,t)+4$ in $O(n)$ time, where a faulty cluster is a connected subgraph of $H_n$ such that all its nodes are faulty. The upper bounds on the length of the path and the time complexity obtained in this paper are optimal.
In this paper, we consider a generalized node-disjoint paths problem: $d$-separated paths problem. In a graph $G$, given two distinct nodes $s$ and $t$, two paths $P$ and $Q$, connecting $s$ and $t$, are $d$-separated if $d_{G-\{s,t\}}(u,v)\geq d$ for any $u\in P-\{s,t\}$ and $v\in Q-\{s,t\}$, where $d_{G-\{s,t\}}(u,v)$ is the distance between $u$ and $v$ in the reduced graph $G-\{s,t\}$. $d$-separated paths problem is to find as many $d$-separated paths between $s$ and $t$ as possible. When $d=1$, $d$-separated paths problem becomes conventional node-to-node disjoint paths problem. In this paper, we give the following results on $d$-separated paths problems on $n$-dimensional hypercubes and star graphs $H_n$ and $G_n$. Given $s$ and $t$ in $H_n$, there are at least $(n-2)$ 2-separated paths between $s$ and $t$. $(n-2)$ is the maximum number of $2$-separated paths between $s$ and $t$ for $d(s,t)\geq 4$. Moreover, $(n-2)$ 2-separated paths of length at most $\min\{d(s,t)+2$, $n+1\}$ for $d(s,t)< n$ and of length $n$ for $d(s,t)=n$ between $s$ and $t$ can be constructed in $O(n^2)$ optimal time. For $d\geq 3$, $d$-separated paths in $H_n$ do not exist. Given $s$ and $t$ in $G_n$, there exist exactly $(n-1)$ 3-separated paths between $s$ and $t$. For $1\leq d\leq 3$, $(n-1)$ is the maximum number of $d$-separated paths between $s$ and $t$ in $G_n$. $(n-1)$ 3-separated paths of length at most $\min\{d(s,t)+4, d(G_n)+2\}$ between $s$ and $t$ can also be constructed in $O(n^2)$ optimal time, where $d(G_n)=\lfloor \frac{3(n-1)}{2}\rfloor$. For $d\geq 5$, $d$-separated paths in $G_n$ do not exist.
Reviewer of IEICE Transactions.
Reviewer of IJFCS.
Program committee member of the 8th International Conference on Parallel and Distributed Computing and Systems.
Program committee member of the 2nd Aizu International Symposium on Parallel Algorithms/Architectures.
Session chair of the 1996 International Conference on Parallel and Distributed Systems.