/ Satoshi Okawa / Professor
/ Valeril V. Trofimov / Visiting Professor
/ Qian Ping Gu / Associate Professor
/ Takafumi Hayashi / 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 L be any class of languages, L' be one of the classes of context-free, context-sensitive, and recursively enumerable languages, and $ \Sigma $ be any alphabet. If the following statement (1) holds, then the statement (2) holds. (1) For any language $ L $ in {\cal L}, there exist an alphabet $ \Gamma $ including $ \Sigma $, a homomorphism $ h: \Gamma^* \rightarrow \Gamma^* $ defined by $ h(a) = a $ for $ a \in \Sigma $ and $ h(a) =\lambda $ for $ a \in \Gamma - \Sigma $, a Dyck language $ D $ over $ \Gamma $, and a language $ L_1 $ over $ \Gamma $ such that $ L = h(D \cap L_1) $. (2) For any language $ L $ in {\cal L}, there exist an alphabet of $ k $ pairs of matching parentheses $ X_k $, Dyck reduction {\it Red} over $ X_k $, and a language $ L_2 $ in {\cal L}' over $ \Sigma \cup X_k $ such that $ L = {\it Red}(L_2) \cap \Sigma^* $.
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. 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.
In this paper, we give an efficient algorithm for the following problem in the $n$-dimensional star graph $G_n$: Given $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 $s_i\rightarrow t_i$, $1\leq i\leq k$. Our algorithm finds the $k$ disjoint paths of length at most $d(G_n)+5$ in $O(n^2)$ optimal time, where $d(G_n)=\lfloor\frac{3(n-1)}{2}\rfloor$ is the diameter of $G_n$. This improves the previous results of $4(n-2)$ (path length) and $O(n^4\log n)$ (time), respectively.
We study node-to-set and set-to-set fault tolerant routing problems in $n$-dimensional hypercubes $H_n$. Node-to-set routing problem is that given a node $s$ and a set of nodes $T=\{t_1,...,t_k\}$, finds $k$ node-disjoint paths $s\rightarrow t_i$, $1\leq i\leq k$. Set-to-set routing problem is that given two sets of nodes $S=\{s_1,...,s_k\}$ and $T=\{t_1,...,t_k\}$, finds $k$ node-disjoint paths, each path connects a node of $S$ and a node of $T$. From Menger's theorem, it is known that these two problems in $H_n$ can tolerate at most $n-k$ arbitrary faulty nodes. In this paper, we prove that both routing problems can tolerate $n-k$ arbitrary faulty subgraphs (called cluster) of diameter 1. For $2\leq k\leq n$, we show that, in the presence of at most $n-k$ faulty clusters of diameter at most 1, the $k$ paths of length at most $n+2$ for node-to-set routing in $H_n$ can be found in $O(kn)$ optimal time and the $k$ paths of length at most $n+k+2$ for set-to-set routing in $H_n$ can be found in $O(kn\log k)$ time. The upper bound $n+2$ on the length of the paths for node-to-set routing in $H_n$ is optimal.
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. Cluster fault tolerant (abbreviated as CFT in what follows) routing studies the number of fault 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 {\it cluster fault diameter} for interconnection networks. We prove that the cluster fault diameter of $H_n$ is $n+2$ when the diameters of the fault 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$.
Given a node $s$ and a set $T=\{t_1,\ldots,t_k\}$ of $k$ nodes in a $k$-connected graph, the node-to-set disjoint paths problem is to find $k$ node-disjoint paths $P_i: s\rightarrow t_i,~1 \leq i \leq k$. In this paper, we give two $O(n^2)$ time algorithms for the node-to-set disjoint paths problem in $n$-dimensional star graphs $G_n$ which are $(n-1)$-connected. We first give a simple algorithm which finds $n-1$ node-disjoint paths of length at most $d(G_n)+3$, where $d(G_n)=\lfloor \frac{3(n-1)}{2}\rfloor$ is the diameter of $G_n$. Then, we refine the algorithm to find $n-1$ node-disjoint paths of length at most $d(G_n)+2$. A lower bound on the length of the paths for the above problem in $G_n$ is $d(G_n)+1$.
Refereed Proceeding Papers
The relation between homomorphic characterization and characterization with Dyck reduction is investigated, and it is found that the homomorphic characterization is a stronger concept than the characterization with Dyck reduction. Furthermore, the relation between the characterization with equality set and the homomorphic one is investigated.
We say a network (graph) can tolerate $l$ faulty nodes for a specific routing problem if after removing at most $l$ arbitrary nodes from the graph, the routing paths exist for the routing problem. However, the bound $l$ is usually a worst-case measure and it is interesting, both practical and theoretical, to find the routing paths when more than $l$ faulty nodes present. Cluster fault tolerant (CFT) routing has been proposed as an approach for this purpose. In CFT routing we try to reduce the number of ``faults'' that a routing problem has to deal with using subgraphs to cover the faulty nodes. In particular, we consider the number and the size (diameter) of faulty subgraphs rather than the number of faulty nodes that a graph can tolerate. We show the necessary and sufficient conditions on the number and the size of faulty subgraphs that the hypercube can tolerate for the following routing problems: find a path from a source node $s$ to a target node $t$; and find $k$ node-disjoint paths from $s$ to $k$ nodes $t_1,...,t_k$. Our results imply that the hypercube can tolerate far more faulty nodes than the worst-case measures for these routing problems when the faulty nodes can be covered by certain subgraphs. We also give algorithms for finding the routing paths for the above routing problems.
An efficient approach for checking the similarity between genomes on a large scale is to compare the order of appearance of identical genes in the two species. The two gene sequences differ not because of local mutations, but because of global rearrangements such as reversals, transpositions, and so on. Given the sequences of the identical genes of two species, if we express one sequence by $I=(12...n)$ then the other sequence can be expressed by a permutation $\pi=(\pi_1\pi_2...\pi_n)$ of $\{1,2,...,n\}$. Checking the similarity between genomes based on global rearrangements leads to a combinatorial problem of finding a shortest series of rearrangements that sorts the permutation $\pi$ into the identity $I$. In this paper, we propose algorithms for permutation sorting by reversals and transpositions.
An {\em undirected routing problem} is a pair $(G, R)$ where $G$ and $R$ are undirected graphs such that $V(G) = V(R)$. A {\em solution} to an undirected routing problem $(G, R)$ is a set $P$ of undirected paths of $G$ such that, for each edge $\{u, v\}$ of $R$, $P$ contains a path between $u$ and $v$. We say that a set of paths $P$ is $k$-colorable if each path of $P$ can be colored by one of the $k$ colors so that the paths of the same color are edge-disjoint (each edge of $G$ appears at most once in the paths of each single color). Let $Q_n$ denote the $n$-dimensional hypercube, for arbitrary $n \geq 1$. We show that a routing problem $(Q_n, R)$ always admits a $4d$-colorable solution where $d$ is the maximum vertex degree of $R$.
In this paper, we study the node-to-node fault tolerant routing problem in the $n$-dimensional hypercube $H_n$ based on the cluster fault tolerant model. For a graph $G$, a faulty cluster is a connected subgraph of $G$ such that all its nodes are faulty. In cluster fault tolerant routing problems, how many faulty clusters and how large of those clusters can be tolerated are studied. It has been known that for the node-to-node routing, $H_n$ can tolerate as many as $n-1$ faulty clusters of diameter at most 1 with at most $2n-3$ faulty nodes in total. In this paper, we extend the above result to show the sufficient conditions on faulty clusters of arbitrary diameters that $H_n$ can tolerate. We also give an algorithm which, given a set of faulty clusters satisfying the sufficient conditions and non-faulty nodes $s$ and $t$ in $H_n$, finds a fault-free path $s\rightarrow t$ of length $d(s,t)+O(\log n)$ in $O(n+|F|)$ optimal time, where $|F|$ is the total number of faulty nodes.
Finding the diameter for a distributed network has numerous applications. Let $G(V,E)$ be an undirected network with $|V|=n$ nodes and $|E|=m$ edges. Performing the breadth first search from an arbitrary node of $G$, one can get an estimation $\tilde{d}(G)$ with $d(G)\leq \tilde{d}(G)\leq 2d(G)$ for the diameter $d(G)$ of $G$. The communication complexity is $O(m)$ and $O(nm)$ for synchronous and asynchronous networks, respectively. To find the diameter $d(G)$, one can perform the breadth first search from all the nodes of $G$ and then find the largest shortest distance between a pair of nodes in $G$. The communication complexity is $O(nm)$ and $O(n^2m)$ for synchronous and asynchronous networks, respectively. In this paper, we give an algorithm which computes an estimation $\tilde{d}(G)$ with $d(G)\leq \tilde{d}(G)\leq d(G)+2$. The communication complexity of our algorithm is $O(n^{2.5})$ and $O(n^{2.5}m^{0.5})$ for synchronous and asynchronous networks, respectively.
Leader election problem is a fundamental problem in distributed computing. The classical leader election problem can be considered as finding the processor with the maximum key in a distributed network in which each processor has one key and a total order is defined on the keys. In this paper, we define a generalized leader election problem which finds all the processors with the maximal keys based on a partial order on the keys. We propose a distributed algorithm for the generalized leader election problem. The algorithm solves the problem on a network using a spanning tree of the network. The message complexity of the algorithm is $O(mn)$, where $m$ is the number of different keys and $n$ is the number of processors.
Leader election problem is a fundamental problem in distributed computing. The classical leader election problem can be considered as finding the processor with the maximum key in a distributed network in which each processor has one key and a total order is defined on the keys. In this paper, we propose a distributed algorithm for a generalized leader election problem which finds all the processors with the maximal keys based on a partial order on the keys. The algorithm solves the problem using a coterie of the $n$ processors. The number of messages exchanged on the coterie is $O(\max\{rn,n^{1.5}\})$, where $r$ is the number of the maximal keys.
This paper presents both new analytical and new numerical solutions to the problem of generating waveforms exhibiting a low peak-to-peak factor. One important application of these results is in the generation of pseudo-white noise signals that are commonly uses in multi-frequency measurements. These measurements often require maximum signal-to-noise ratio while maintaining the lowest peak-to-peak excursion. The new synthesis scheme introduced in this paper uses the Discrete Fourier Transform (DFT) to generate pseudo-white noise sequence that theoretically has a minimized peak-to-peak factor, $F_{p-p}$. Unlike theoretical works in the literature, the method presented here is based in purely discrete mathematics, and hence is directly applicable to the digital synthesis of signals. With this method the shape of the signal can be controlled with about $\sqrt{N}$ parameters given N harmonic components. A different permutation of the same set of offset phases of the ``source harmonics''%$\{\psi_{\kappa}\}_{\kappa=1}^{\sqrt{N}-1}$ creates an entirely different sequence.
Grants
Academic Activities
Others