Next: Language Processing Systems Lab Up: Department of Computer Previous: Mathematical Foundation of ...

Foundation of Computer Science Laboratory


/ 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

  1. Hirose, S., Okawa, S., and Kimura, H., Dyck Reductions are More Powerful Than Homomorphic Characterizations. IEICE Transaction on Information and Systems, vol.E80-D, No.9, p.958--961, 1997.

    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^* $.

  2. Q.P. Gu, S. Peng, and H. Sudborough, A 2-approximation algorithm for genome rearrangements by reversals and transpositions. Theoretical Computer Science, accepted, 1997.

    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.

  3. Q.P. Gu and S. Peng, An efficient algorithm for $k$-pairwise disjoint paths problem in star graphs. Theoretical Computer Science, accepted, 1997.

    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.

  4. Q.P. Gu and S. Peng, Node-to-set and set-to-set cluster fault tolerant routing in hypercubes. Parallel Computing, accepted, 1997.

    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.

  5. Q.P. Gu and H. Tamaki, Routing a permutation in the hypercube by two sets of edge-disjoint paths. Journal of Parallel and Distributed Computing,, Vol.44, p.147-152, 1997.

    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.

  6. Q.P. Gu and S. Peng, $k$-Pairwise cluster fault tolerant routing in hypercubes. IEEE Trans. on Computers, Vol.46, No.9, p.1042-1049, 1997.

    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$.

  7. Q.P. Gu and S. Peng, Node-to-set disjoint paths problem in star graphs. Information Processing Letters, vol.62, p.201-207, 1997.

    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

  1. Okawa, S. and Hirose, S., On the Relation of Homomorphic Characterization and Dyck Reduction. 1st Symposium on Algebra, Languages and Computation, editor: Imaoka, T. and Nehaniv, C., p.1--8, Nov. 1997.

    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.

  2. Q.P. Gu and S. Peng, Cluster fault tolerant routing in hypercubes. Proc. of 1998 International Conference on Parallel Processing (ICPP'98), to appear, 1998.

    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.

  3. Q.P. Gu, S. Peng, and Q.M. Chen, Sorting permutations and its applications in genome analysis. Proc. of Mathematical and Computational Biology Workshop (MCB'97), LLSCI of AMS, to appear, 1998.

    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.

  4. Q.P. Gu and H. Tamaki, Edge-disjoint routing in the undirected hypercube. Proc. of International Symposium on Algorithms and Computations (ISAAC'97), LNCS 1350, p.72-81, 1997.

    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$.

  5. Q.P. Gu and S. Peng, Node-to-node cluster fault tolerant routing in hypercubes. Proc. of International Symposium on Parallel Algorithms and Networks (ISPAN'97), p.404-409, 1997.

    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.

  6. Q.P. Gu and Z. Cheng, Efficient estimation of diameter for distributed networks. Proc. of the 11th Annual International Symposium on High Performance Computing Systems, p.261-268, 1997.

    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.

  7. Z. Cheng and Q.P. Gu, A distributed algorithm for leader election from a partially ordered set. Proc. of the 11th Annual International Symposium on High Performance Computing Systems, p.253-260, 1997.

    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.

  8. Z. Cheng and Q.P. Gu, A distributed algorithm for leader election from a partially ordered set on a coterio. Proc. of International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA'97), 1997.

    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.

  9. Hayashi, T., High energy density pseudo noise. Proceedings of the meeting of SIAM Japan, Japan SIAM, Oct., 1997.

    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.

  10. Ohtake, Y., and Yukita, S., A Dual Visualizer Method for Interactive Topology. MultiMedia Modeling '98, IEEE Computer Society Press, p.163-172, Oct., 1998.

Grants

  1. Qian Ping Gu, Ministry of Education Scientific Research Fund, Priority Area, Genome Science, Thesis No. 09272221.

  2. Takafumi Hayashi, Ministry of Education Scientific Research Fund, for Young Researchers (A), Engineering, Mechanical Engineering, Thesis No. 09750083.

  3. Shuichi Yukita, Research/Educational Project supported by Fukushima Prefectural Foundation for the Advancement of Science and Education.

Academic Activities

  1. Satoshi Okawa, Served as a reviewer of IEICE Transactions, 1997.

  2. Takafumi Hayashi, GNU Fortran developper, 1997.

  3. Takafumi Hayashi, Contribution to GNU Plotutils, 1997.

  4. Takafumi Hayashi, Contribution to Free Software Foundation, 1997.

Others

  1. Yatsuyanagi, H., A Case Study of Algorithm Visualization: Dijkstra Algorithm, Univ. of Aizu 1998, Thesis Advisor: Satoshi Okawa.

  2. Hoshi, Ch., On Graph Family Defined from Trivalent Cayley Graph. Univ. of Aizu 1998, Thesis Advisor: Satoshi Okawa.

  3. Yamazaki, A., Pancake Graphs: their Diameters and Cycles. Univ. of Aizu 1998. Thesis Advisor: Satoshi Okawa.

  4. H. Fujiguchi, Node-to-node fault tolerant routing in hypercubes. The Univ. of Aizu, 1997. Thesis Advisor: Qian Ping Gu.

  5. Y. Tosaka, Cluster fault tolerant routing in hypercubes. The Univ. of Aizu, 1997. Thesis Advisor: Qian Ping Gu.

  6. Y. Yamamoto, A heuristic algorithm for genome rearrangements. The Univ. of Aizu, 1997. Thesis Advisor: Qian Ping Gu.

  7. H. Kuninobu, An empirical study on algorithms for genome rearrangements. The Univ. of Aizu, 1997. Thesis Advisor: Qian Ping Gu.

  8. Sato, N., Low Peak Factor Pseduo-white Noise Synthesis and its Application to Spread Spectrum Communication. The Univ. of aizu, 1997, Thesis Advisor: Takafumi Hayashi.

  9. Shibata, C., Low Peak Factor Pseduo-white Noise Synthesis and its Application to Multi Frequency Measurement. The Univ. of aizu, 1997. Thesis Advisor: Takafumi Hayashi.

  10. Kurita, Low Peak Factor Pseduo-white Noise Synthesis: Noise as Random number Sequence. The Univ. of aizu, 1997. Thesis Advisor: Takafumi Hayashi.

  11. Hashimoto, H., Construction of The Nearest Neighbor Point Groups. The Univ. of aizu, 1997. Thesis Advisor: Takafumi Hayashi.

  12. Miura, S., Distributed Computing for Mathematical Visualization. The Univ. of Aizu, 1997, Thesis Advisor: Shuichi Yukita.

  13. Furuya, K., Interactive Visualizer of Minimal Surfaces. The Univ. of Aizu, 1997, Thesis Advisor: Shuichi Yukita.

  14. Anazawa, S., Visualization of Surgery on Closed Surfaces. The Univ. of Aizu, 1997, Thesis Advisor: Shuichi Yukita.

  15. Miyajima, K, The Examination of Work Efficiency in Making Textures. The Univ. of Aizu, 1997, Thesis Advisor: Shuichi Yukita.



Next: Language Processing Systems Lab Up: Department of Computer Previous: Mathematical Foundation of ...


www@u-aizu.ac.jp
December 1998