29th IEEE International Symposium on Multiple-Valued-Logic 1999 Freiburg im Breisgau Germany 20-22 May 1999 PROGRAM Location Institute of Computer Science Albert-Ludwigs-University Freiburg Building 101 Am Flughafen 17 79110 Freiburg, Germany Organizing Committee Rolf Drechsler, Symposium Chair Bernd Becker, Symposium Co-Chair Nicole Drechsler, Financial Chair Frank Schmiedle, Publication Chair Christoph Scholl, Local Arrangement Chair Institute of Computer Science Albert-Ludwigs-University, Freiburg, Germany Program Chairs Elena Dubrova, Program Chair Europe/Africa Royal Institute of Technology, Sweden Michael Miller, Program Chair Americas University of Victoria, Canada Takahiro Hanyu, Program Chair Asia/Pacific Tohoku University, Japan Sponsors We wish to thank the following for their contribution to the success of this conference: IEEE Computer Society. Albert-Ludwigs-University of Freiburg, Germany. Technical Committee on Multiple-Valued Logic. European Office of Aerospace Research and Development. Air Force Office of Scientific Research. United States Air Force Research Laboratory. Activities Wednesday May 19 ULSI Workshop Conference registration Welcome reception Thursday May 20 Conference registration Technical sessions of ISMVL 99 Welcome reception in Freiburg Friday May 21 Technical sessions of ISMVL 99 Organo concert (Freiburger Muenster) Conference banquet Saturday May 22 Technical sessions of ISMVL 99 Welcome to ISMVL 99 Welcome to Freiburg im Breisgau, the site of the 29th International Symposium on Multiple-Valued Logic. Freiburg is a period middle-ages city founded by the Dukes of Zaehringen (the right to hold markets was granted in 1120 A.D.). Its historical development was especially influenced by its more than 400- year-long association with the Habsburg Dynasty. The city developed from a walled middle-ages market town to a fort city (17th/18th century) to the present-day modern city of about 200,000 inhabitants. It is the first time that the symposium is being held in Germany. Like in the past years researchers from different areas discuss the latest results in the field of multiple- valued logic. The symposium is co-sponsored by the Albert- Ludwigs-University, Freiburg, the IEEE Computer Society, the Japan Research Group on Multiple-Valued Logic (JRG-MVL), and the European Office of Aerospace Research and Development (EOARD). We wish to express our gratitude to the Symposium Committee for their hard work in preparing this event. Dr. Elena Dubrova served as a Program Chair for Europe and Africa, Prof. Takahiro Hanyu served as a Program Chair for Asia and Australia, and Prof. Michael Miller served as a Program Chair for the Americas. We would like to thank them for organizing an excellent program. ISMVL'99 has been the joint effort of many people. We especially like to thank Nicole Drechsler (Financial Chair), Frank Schmiedle (Publication Chair), and Dr. Christoph Scholl (Local Arrangement Chair). Finally, we would like to wish all participants a beautiful time in Freiburg and the black forest area and hope that we will have many stimulating discussions. Rolf Drechsler Bernd Becker Symposium Chair Symposium Co-Chair Workshop on Post-Binary ULSI Systems Wednesday, 19 May 10:00 - 10:20 Registration 10:20 - 10:30 Opening remarks Room 00-036 T. Waho, Workshop Organizer Session 1: Invited Talks Room 00-036 Chair: G. Gulak 10:30 - 11:15 Innovation of Intelligent Integrated Systems Architecture -Future Challenge M. Kameyama, Tohoku University, Japan 11:15 - 12:00 Quantum Electronic Circuit Concepts by Nanometric Technology H. Hartnagel, Technical University of Darmstadt, Germany 12:00 - 13:00 Lunch Session 2: Nanoelectronics Room 00-036 Chair: T. Waho 13:00 - 13:20 High-Speed Single-Electron Memory and Logic H. Mizuta, K. Tsukagoshi, K. Nakazato, H. Ahmed, Hitachi Cambridge, UK 13:20 - 13:40 Programmable HBT-Quantum Dot Structures for Arithmetic MVL L. Micheel, Wright Lab., USA, A. Sigurdardottir, H. Hartnagel and K. Mutamba, Technical University of Darmstadt, Germany 13:40 - 14:00 GaAs- and InP-based Technologies of Resonant Tunneling Devices O. Dupuis, P. Mounaix, F. Mollot, O. Vanbesien, D. Lippens, IEMN, France 14:00 - 14:20 Nano-Fabrication Technology and Silicon Nano-Devices T. Baba, NEC Corporation, Japan 14:20 - 14:40 Refreshment break Session 3 : BDD/MDD Room 00-036 Chair: C. Scholl 14:40 - 15:00 Nonapproximability Results for OBDD- and FBDD-Minimization D. Sieling, University of Dortmund, Germany 15:00 - 15:20 Improving Reachability Analysis by means of Activity Profiles G. Cabodi, P. Camurati, S. Quer, Politecnico di Torino, Italy 15:20 - 15:40 A Word-Level Graph Representation Package S. Hoereth, Siemens, Germany 15:40 - 16:00 Interval Diagram Techniques and Their Applications K. Strehl, L. Thiele, ETH Zuerich, Switzerland 16:00 - 16:20 Refreshment break Session 4: Application of Information Theory to Logic Design Room 00-036 Chair: S. Yanushkevich 16:20 - 16:40 Information Theory Approach in Logic Design: Results, Trends and Non-Solved Problems S. Yanushkevich,Technical University of Szczecin, Poland, D. Simovici, University of Massachusetts at Boston, USA 16:40 - 17:00 Methods of Information Engine Theory in Simple Examples H. Watanabe, Soka University Tokyo, Japan, S. Yanushkevich, Technical University of Szczecin, Poland 17:00 - 17:20 Information Measure in Evolvable Algorithm for Synthesis of Combinational Circuits C. Moraga, University of Dortmund, Germany, J. Kolodziejczyk, M. Opoka, S. Yanushkevic, Technical University of Szczecin, Poland 17:20 - 17:40 Information Theoretical Approach in Reed- Muller Expansion Minimization D. Popel, Belarusian State University of Informatics and Radioelectronics, Belarus, V. Shmerko, S.Yanushkevich, Technical University of Szczecin, Poland 18:00 ISMVL99 welcome reception Conference Thursday, May 20 8:45 - 9:00 Opening remarks Room 00-036 R. Drechsler, Symposium Chair B. Becker, Director CS-Institute, University of Freiburg, Germany Session 1: Invited address Room 00-036 Chair: T. Hanyu 9:00 - 10:00 Development of Quantum Functional Devices for Multiple-Valued Logic Circuits T. Baba, NEC Corporation, Japan 10:00 - 10:30 Refreshment break Session 2a: Algebra I Room 00-036 Chair: I. Rosenberg 10:30 - 11:00 Multivalued Binary Relations and Post Algebras M. Serfati, University of Paris, France 11:00 - 11:30 On Axiomization of Conditional Entropy of Functions Between Finite Sets D. Simovici, S. Jaroszewicz, University of Massachusetts at Boston, USA 11:30 - 12:00 Quaternion Groups versus Dyadic Groups in Representations and Processing of Large Switching Functions R. Stankovic, D.Milenovic, D. Jankovic, University of Nis, Yugoslavia Session 2b: Circuits Room 00-010 Chair: Y. Hata 10:30 - 11:00 Multiple-Valued Content-Addressable Memory Using Metal-Ferroelectric- Semiconductor FETs T. Hanyu , H. Kimura, M. Kameyama, Tohoku University, Japan 11:00 - 11:30 New Lamps for Old! (Generalized Multiple- Valued Neurons) C. Moraga, R. Heider, University of Dortmund, Germany 11:30 - 12:00 Supplementary Symmetrical Logic Circuit Structure E. Olson, Moorpark, USA 12:00 - 13:30 Lunch (Executive Subcommittee Meeting) Session 3a: Decomposition Room 00-036 Chair: J. Muzio 13:30 - 14:00 Bi-Decomposition of Multi-Valued Functions for Circuit Design and Data Mining Applications B. Steinbach, University of Freiberg, Germany, M. Perkowski, Portland State University, USA, C. Lang, University of Freiberg, Germany 14:00 - 14:30 Totally Undecomposable Functions: Applications to Efficient Multiple-Valued Decompositions T. Sasao, Kyushu Institute of Technology, Japan 14:30 - 15:00 A Generalization of Shestakov's Function Decomposition Method J. Lou, ThoughtWorks Inc., USA, J. Brzozowski, University of Waterloo, Canada Session 3b: Clones Room 00-010 Chair: G. Pogosyan 13:30 - 14:00 Gigantic Pairs of Minimal Clones I. Rosenberg, University of Montreal, Canada, H. Machida, Hitotsubashi Unversity, Japan 14:00 - 14:30 Maximal Chains of Partial Clones Containing Idempotent Partial Functions L. Haddad, J. Fugere, Royal Military College of Canada 14:30 - 15:00 Partial Clones and their Generating Sets L. Haddad, Royal Military College of Canada, D. Lau, University of Rostock, Germany 15:00 - 15:30 Refreshment break Session 4a: Logic Design Room 00-036 Chair: C. Moraga 15:30 - 16:00 Evaluation of m-Valued Fixed Polarity Generalizations of Reed-Muller Canonical Forms E. Dubrova, Royal Institute of Technology, Sweden 16:00 - 16:30 Multiple-Valued Minimization to Optimize PLAs with Output EXOR Gates D. Debnath, T. Sasao, Kyushu Institute of Technology, Japan 16:30 - 17:00 The Output Permutation for the Multiple- Valued Logic Minimization with Universal Literals T. Hozumi, O. Kakusho Hyogo University, Y. Hata, Himeji Institute of Technology, Japan 17:00 - 17:30 Logic Model for Representing Uncertain Statuses of Multiple-Valued Logic Systems Realized by Min, Max and Literals N. Takagi, A. Hon-nami, K. Nakashima, Toyama Prefectural University, Japan Session 4b: Algebra Room 00-010 Chair: R. Haehnle 15:30 - 16:00 A Super Switch Algebra for Quantum Device based Systems G. Dueck, University of Antigonish, M. Hu, Aepos Technologies, B. Fraser, University of Antigonish, Canada 16:00 - 16:30 Clarifying the Axioms of Kleene Algebra based on the Method of Indeterminate Coefficients T. Ninomiya, M. Mukaidono, Meiji University, Japan 16:30 - 17:00 The Number of Cascade Functions G. Pogosyan, Christian University, Japan 17:00 - 17:30 Research on the Similarity among Precomplete Sets Preserving m-ary Relation in Partial K-Valued Logic L. Renren, Xiangtan University of Hunan, China 18:30 Welcome reception in Freiburg Friday, May 21 Session 5: Invited Address Room 00-036 Chair: E. Dubrova 9:00 - 10:00 Automata, Circuits and BDDs D. Basin, University of Freiburg, Germany 10:00 - 10:15 Refreshment break Session 6a: Decision Diagrams Room 00-036 Chair: R. Drechsler 10:15 - 10:45 Synthesis of Multiple-Valued Decision Diagrams using Current-Mode CMOS Circuits M. Abd-El-Barr, King Fahd University of Dhahran, Saudi Arabia, H. Fernandes, University of Saskatchewan, Canada 10:45 - 11:15 Shared Multiple-Valued Decision Diagrams for Multiple-Output Functions H. Md. H. Babu, T. Sasao, Kyushu Institute of Technology, Japan 11:15 - 11:45 Matrix-Valued EXOR-TDDs in Decompositon of Switching Functions R. Stankovic, University of Nis, Yugoslavia Session 6b: Circuits II Room 00-010 Chair: M. Kameyama 10:15 - 10:45 Ternary Multiplication Circuits Using 4-Input Adder Cells and Carry Look-Ahead A. Herrfeld, S. Hentschke, University of Kassel, Germany 10:45 - 11:15 Down Literal Circuit with Neuron-MOS Transistors and Its Applications J. Shen, K. Tanno, O. Ishizuka, Miyazaki University, Japan 11:15 - 11:45 Arithmetic Circuits for Analog Digits A.Saed, Nortel Networks, Canada, M. Ahmadi, G. Jullien, University of Windsor 11:45 - 13:00 Lunch (Symposium Subcommittee Meeting) Session 7a: Applications Room 00-036 Chair: R. Stankovic 13:00 - 13:30 Quaternary Coded Genetic Algorithms K. Freitag, SAG Systemhaus GmbH, L. Hildebrand, C. Moraga, University of Dortmund, Germany 13:30 - 14:00 Redundant Complex Arithmetic and Its Application to Complex Multiplier Design T. Aoki, K. Hoshi, T. Higuchi, Tohoku University, Japan 14:00 - 14:30 On the Number of Multilinear Partitions and the Computing Capacity of Multiple-Valued Multiple-Threshold Perceptrons A. Ngom, Lakehead University, Canada, I. Stojmenovi, University of Ottawa, Canada, J. Zunic, University of Novi Sad, Yugoslavia 14:30 - 14:45 Refreshment break 14:45 - 15:15 B-ternary Logic Based Asynchronous Micropipeline Y. Nagata, University of the Ryukyus, Japan, M. Miller, University of Victoria, Canada, M. Mukaidono, Meiji University, Japan 15:15 - 15:45 State Assignment Techniques in Multiple- Valued Logic K. Adams, J. Campbell, L. Maguire, J. Webb, University of Ulster, Northern Ireland, UK Session 7b: Logic Room 00-010 Chair: L. Haddad 13:00 - 13:30 Information Relationships and Measures in Application to Logic L. Jozwiak, Eindhoven University of Technology, The Netherlands 13:30 - 14:00 Probabilistic and Truth-Functional Many- Valued Logic Programming T. Lukasiewicz, University of Gieﾟen, Germany 14:00 - 14:30 Representation Theorems and Theorem Proving in Non-Classical Logics V. Sofronie-Stokkermans, Max-Planck-Institut Saarbruecken, Germany 14:30 - 14:45 Refreshment break 14:45 - 15:15 Transformations between Signed and Classical Clause Logic B. Beckert, R. Haehnle, University of Karlsruhe, Germany, F. Manya, University of Lleida, Spain 15:15 - 15:45 Semirigidity Problems in k-Valued Logic M. Miyakawa, Tsukuba College of Technology, Japan 15:45 - 16:30 Plenary Session Room 00-036 G. Dueck, University of Antigonish, Canada 16:30 Social event Saturday, May 22 Session 8: Panel Discussion Room 00-036 Chair: J. Muzio 9:00 - 10:00 Multiple-Valued Logic in the Next Millenium: Challenges and Perspectives 10:00 - 10:30 Refreshment break Session 9a: Testing Room 00-036 Chair: T. Sasao 10:30 - 11:00 Fault Characterization and Testability Considerations in Multi-Valued Logic Circuits M. Abd-El-Barr, M. Al-Sharif, M. Osman, King Fahd University of Dhahran, Saudi Arabia 11:00 - 11:30 Highly Testable Group Based Logic Circuits U. Kalay , M. Perkowski, D. Hall, Portland State University, USA 11:30 - 12:00 Self-Checking Multiple-Valued Circuit Based on Dual-Rail Current-Mode Differential Logic T. Hanyu , T. Ike, M. Kameyama, Tohoku University, Japan Session 9b: Fuzzy Logic Room 00-010 Chair: O. Ishizuka 10:30 - 11:00 On the Concept of Qualitative Fuzzy Sets H. Thiele, University of Dortmund, Germany 11:00 - 11:30 On Some Classes of Fuzzy Information Granularity and Their Representations Y. Hata, Himeji Institute of Technology, M. Mukaidono, Meiji University, Japan 11:30 - 12:00 From a Fuzzy Flip-Flop to a MVL Flip-Flop L. Maguire, T. McGinnity, L. McDaid, University of Ulster, Northern Ireland, UK 12:00 - 12:15 Closing remarks Room 00-036 Notes Map