Foundation of Computer Science Laboratory

/ Qian Ping Gu / Professor
/ Sergei Duzhin / Visiting Professor
/ Zoltan Esik / Visiting 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.

• Algorithms and computation;
• 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;
• Machine learning;
• Dynamical systems in discrete mathematics: and
• Formal Languages.

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, fault tolerant routing in computer/communication networks, multicolor routing on all-optical networks, 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 three SCCP projects in this laboratory:

• Concrete Mathematics, supervised by Prof. Yukita. 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.
• PC-UNIX and Networking, supervised by Prof. Yukita. 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.
• Inteructive Multimedia Datebase by Prof. Takafumi Hayashi. The project is research and development of multimedia contents.
• 3D Measurement by Prof. Takafumi Hayashi. The project is research and development of 3D measurement and 3D modelling.
• Net-Sys Administtration by Prof. Takafumi Hayashi. The project is research and development about the system administration.

Refereed Journal Papers

1. Qianping Gu and Shietung Peng., An Efficient Algorithm for $k$-Pairwise Disjoint Paths in Hypercubes. Journal of Parallel and Distributed Computing, accepted, 2000.

2. Qianping Gu and Hisao Tamaki., Multicolor Routing in the Undirected Hypercube. Discrete Applied Mathematics, vol.100, pp.169-181, 2000.

3. Qianping Gu and Shietung Peng., Cluster fault tolerant routing in star graphs. NETWORKS, vol.35, No.1, pp.83-90, 2000.

4. Qianping Gu and Shietung Peng., Unicast in hypercubes with large number of faulty nodes., IEEE Trans. on Parallel and Distributed Systems, vol.10, No.10, pp.964-975, 1999.

5. Hayashi, T. and Martens W.L., The synthesis of low-peak cross-correlation sequences using trigonometric function aliasing. IEICE Trans. Fundamentals, vol.E82-A, No.8, pp.1402--1411, 1999.

1. Qianping Gu and Shietung Peng., Efficient protocols for permutation routing on all-optical multistage interconnection networks. Proc. of 2000 International Conference on Parallel Processing (ICPP2000), to appear, 2000.

2. Qianping Gu and Shietung Peng., Wavelengths Requirement for Permutation Routing on All-Optical Multistage Interconnection Networks. Proc. of International Parallel and Distributed Processing Symposium (IPDPS2000), pp.761-768, 2000.

3. Satou , N. and Hayashi, T., Color Image Recognition based on intelectual human vision model. SII99, pp.309--314, SII, Jun. 1999.

4. Hayashi, T., Orthogonal base set low peak white noise and its applications. SII99, pp.107--113, IEICE, Nov. 1999.

Grants

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

Academic Activities

1. Takafumi Hayashi., Member of the Working group on image processing of IEE.

2. Qian Ping Gu., Vice chair of program committee of the 2000 International Conference on Parallel and Distributed Systems (ICPADS2000), 1999.

3. Qian Ping Gu., Vice chair of program committee of the 2000 International Symposium on Parallel Architectures, Algorithms, and Networks (ISPAN2000), 1999.

Others

1. Hachiro MEGURO., Image processing for an effective 3D measurement. Univ. of aizu, Thesis Advisor: T. Hayashi. 1999.

2. Masaomi Koyanagi., Low peak cross correlation using trigonometric aliasing and its application to A-CDMA. Univ. of aizu, Thesis Advisor: T. Hayashi. 1999.

3. Riyou Hyakutake., Low peak cross correlation using trigonometric aliasing and its application to S-CDMA. Univ. of aizu, Thesis Advisor: T. Hayashi. 1999.

4. Daisuke Yoshida., Orthogonal Low-Peak Pseudo White Noise using Trigonometric Aliasing and its Application to S-CDMA. Univ. of aizu, Thesis Advisor: T. Hayashi. 1999.

5. Hiroki Tano., Robust processing of stereo images for a 3D measurement. Univ. of aizu, Thesis Advisor: T. Hayashi. 1999.

6. Takeru Oowada., Low Peak Factor Pseudo-white Noise Synthesis and its Minimum Peak of Transmitting Waveforms. Univ. of aizu, Thesis Advisor: T. Hayashi. 1999.