/ Yin Seong Ho / Visiting Professor
/ Adam Kapralski / Associate Professor
/ Zbigniew Kokosinski / Assistant Professor
The Mathematical Foundation of Computer Science Laboratory is conducting research and teaching basic theoretical subjects which have deep mathematical backgrounds and wide applications. The main goals of the laboratory are the development of Depth Search Machines (DSMs), their applications, and related supplementary topics. DSMs contain different architectures and different simulators. The basic principles of architecture and processing are taught using a book on parallel and sequential processing in DSMs published last year.
The architecture of DSMs contains the main processor which is the MEMRC device, and other supplementary devices. The most important is a hardware generator of combinatorial objects. Applications of DSMs contain methods of representation and methods of processing different tasks related to particular branches of computer science. Among many possible applications till now, the main focus is on geometrical processing in DSMs and on processing NP-complete and isomorphic complete problems. The top-down courseware on Geometrical Processing in Depth Search Machines is being developed by the laboratory. The second project which belongs to the laboratory is the group research project entitled Depth Search Machines. The main goal to be reached in Geometrical Processing in Depth Search Machines is the development of a new course which concerns geometrical processing itself and its applications for AI. The main topics, include developing representations of geometrical figures, evaluations of short paths and their usage for pattern recognition and machine intelligence. DSMs create a very convenient environment for implementing geometrical processing. It is enough to say that most of the algorithms for even advanced applications have a running time of O(1).
The main focus in the project Depth Search Machines is the generation of combinatorial objects in parallel. The developed methods concern the basic background and also hardware generators which are seen as special implementations of the developed methods. Currently there is offered a Student Extracurricular Project (SCCP) on Processing in Depth Search Machines for freshmen.
Teaching logic design is also related to Depth Search Machines, since the proposed methods drawn from the theory of boolean spaces can be very effectively processed in DSMs, as far as processing a single submatrix is concerned. But for solving most of the problems, parallel generation of combinatorial objects enables the development of massively parallel processing. Problems related to logic design create a wide family of practical applications of one general NP-complete problem which is called DIFFERABILITY. That basic program of the laboratory is performed by Profs. Adam Kapralski and Zbigniew Kokosinski.
Presence of Visiting Professor Yin-Seong Ho in the laboratory enriched the general profile of the laboratory, since his main interest is focused on knowledge representation and its processing. Professor Ho, during his stay at the University of Aizu, published numerous conference papers.
Refereed Proceeding Papers
In this paper a computer simulation of parallel generation of permutations, combinations (k-subsets) and partitions (all with no more then m blocks) of the set {1,2, ... ,r}, 1 $\leq$ m,k $\leq$ r $\leq$ n, is applied for experimental verification of the theoretical analysis of parallel computations given by Flatt and Kennedy. Three basic performance measures are used throughout the paper: parallel computation time T(NP), parallel cost penalty Q(NP) and cost over speedup Z(NP), where NP denotes the number of processors. Minimum value of Z(NP) allows us to determine the operating point. All performance measures are presented on diagrams. It is shown that the problem of parallel generation of combinatorial configurations may be efficiently solved in the SIMD model. Moreover, we can derive conclusions about the performance of computations in depth search machines for processing a class of NP-complete and Isomorphic-complete problems having common representation in the form of Boolean matrices.
In this paper a versatile hardware generator of combinatorial objects has been described to provide fast mask and pattern generation for associative processors. The generation of combinatorial objects is treated as a process of generation of states in the interconnection network. One object (permutation, k-subset, partition) is generated in one step. As a model of parallel computations the parallel counter model is used. The proposed device consists of a versatile programmable commutative block and a versatile programmable control block. In the generator regular cellular structures of both the control circuit and the cellular array overlap. This property seems to be very important from the point of view of VLSI design requirements.
Zbigniew Kokosinski. Invention certificate. Digital generator for data permutation in RAM memory, publisher: Patent Office of the Republic of Poland 161547, Zbigniew Kokosinski, Poland, May 1994.
Member of Editorial Board of International Journal of SHAPE MODELING, World Scientific Publisher.