 |
Dr. Tadeusz Strzemecki
Assistant Professor
Department of Computer & Information Sciences
815-A Lowenstein
113 W60th St., New York NY 10023
Email: ts(at)dsm.fordham.edu
Phone: 212-636-6332
|
Research
The most immediate objective of the conducted research is the
development of the new and efficient method for the exact solution for
the Minimum Disjunctive Normal Form (MDNF) problem. The research on
the new method for the generation of prime implicants, which has
already been completed, was the first and necessary step for finding a
solution for the MDNF problem. The research on the solution for the
MDNF problem has been, to some extent, conducted simultaneously with
the research on the new method for the generation of prime implicants.
This has been possible because the problem of prime implicants
generation is considered to be an intrinsic part of the solution for
the MDNF problem. The research on the solution for the MDNF problem is
already advanced in the sense that the methodology, notation, proof
techniques, as well as the simulation programs, have already been
developed. There exist also some conjectures as to what algorithms
for the MDNF problem would constitute a solution. What remains is to
refine the conjectured solution, and to provide the correctness proof
of the proposed approach. In case of the successful completion of the
immediate research goal, i.e. the solution for the MDNF problem, the
research would be carried out even further. The next goals would
include extensions of the proposed approach to Boolean functions in
various other representations and to multiple-output Boolean
functions, and application of the research on Boolean functions to
problems in graph theory. The possible successful extension of the
research to problems in graph theory is indicated by the already
established close relation of the proposed method to the solution for
the CLIQUE problem in boolean graphs.Selected Publications
-
T. Strzemecki (1992). "Polynomial-Time Algorithms for Generation of Prime Implicants", Journal of Complexity, 8(1):37-63
-
T. Strzemecki (1993). "A Linear Upper Bound on the Number of Prime Implicants", International Symposium for Young Computer Scientists, Beijing, China, July, 1993.
-
T. Strzemecki (1991). "Construction of Small-Depth Circuits", Proceedings of the International Conference for Young Computer Scientists, 312-316, Beijing, China, July, 1991.
-
X. Li, T. Strzemecki, B. Fang, and T. Qin (1989). "A New Result for an Old Problem - How Many Prime Implicants Are There in a Boolean Function?", Proceedings of Beijing International Symposium for Young Computer Profesionals, 616-619, August, 1989.
|
|
