Advance Program
IFIP WG 10.5 Workshop on
Applications of the Reed-Muller Expansions in Circuit Design
Fujitsu Makuhari Systems Laboratory, Chiba City, Chiba 261, Japan.
27th -29th August, 1995.

                      Sunday, August 27

  15:00-18:00  Registration / Poster preparation

  18:00-20:00  Reception (For students 4000 YEN)

                       Monday, August 28

  8:30-9:00  Registration / Poster preparation

  9:00-9:20  Welcome 
             Tsutomu Sasao, Masahiro Fujita

  9:20-10:20  Session 1: Representation of Discrete Functions I. 
                         Chair: W. Rosenstiel

          &  Graph-based representations of discrete functions,
             Shin-Ichi Minato (NTT LSI Lab.)*
          &  Representation of logic functions using EXOR operators,
             Tsutomu Sasao (Kyushu Institute of Technology)*

  10:20-10:40  Break / Poster

  10:40-11:40  Session 2: Decision Diagrams I.
                          Chair: Bernd Becker

          &  Application of MTBDD to spectral transformations,
             E. M. Clarke,
             Z. Xudong (Carnegie Mellon University) and 
             M. Fujita (Fujitsu Laboratories of America Inc.)*
          &  A zero-suppressed BDD package with pruning and its 
             application to GRM minimization,
             Hiroyuki Ochi (Hiroshima City University)
          &  The theory of zero-suppressed BDDs and the number of 
             knight's tours,
             Martin Lobbing, Olaf Schroer and Ingo Wegener (Univ. Dortmund)
          &  Spectral transforms decision diagrams,
             Radomir S. Stankovic (University of Nis), 
             Tsutomu Sasao (Kyushu Institute of Technology) and 
             Claudio Moraga (Dortmund University)

  11:40-12:00  Poster

  12:00-13:00  Lunch

  13:00-14:30  Session 3: ESOP Minimization.
                          Chair: Udo Kebschull

          &  Applications of graph based representations,
             Fabio Somenzi (University of Colorado)*
          &  Synthesis of AND-EXOR expressions via satisfiability,
             Mario Escobar and 
             Fabio Somenzi (University of Colorado)
          &  A simplification algorithm of AND-EXOR expressions for 
             multiple-output functions,
             Takashi Hirayama and Yasuaki Nishitani (Gunma University)
          &  An upper bound on the number of products in minimum ESOPs,
             Norio Koda (Tokuyama College of Technology) and 
             Tsutomu Sasao (Kyushu Institute of Technology)
          &  Application of ESOP minimization in machine learning and 
             knowledge discovery,
             Marek A. Perkowski (Portland State University),
             Timothy Ross,
             Dave Gadd,
             Jeffrey A. Goldman (Wright Laboratory) and 
             Ning Song (Lattice Logic Corp.)
          &  ACEM: A minimization method for exclusive-OR sum of 
             products expressions,
             Samuel E. Aborhey (University of The South Pacific)
          &  An efficient data structure for the minimization of EXOR sums,
             Jonathan Saul (Oxford University)

  14:30-15:30  Break / Poster

  15:30-17:00  Session 4: Decision Diagrams II.
                          Chair: Jonathan Saul

          &  Efficient computation of the probability and 
             Reed-Muller spectra of Boolean functions using 
             edge-valued binary decision diagrams,
             Sarma B. K. Vrudhula (University of Arizona),
             Yung-Te Lai and 
             Massoud Pedram (University of Southern California)*
          &  On an arithmetic transform of Boolean functions,
             Jawahar Jain (Fujitsu Laboratories of America)*
          &  Ternary decision diagrams to represent ringsum-of-products forms,
             Koichi Yasuoka (Kyoto University)
          &  On variable ordering and decomposition type choice in OKFDDs,
             Rolf Drechsler (Johann Wolfgang Goethe-University),
             Bernd Becker (University of Freiburg) and 
             Andrea Jahnke (Johann Wolfgang Goethe-University) 
          &  Dynamic minimization of OKFDDs,
             Rolf Drechsler (Johann Wolfgang Goethe-University) and 
             Bernd Becker (University of Freiburg)

  17:00-17:30  Poster

  18:00-20:00  Banquet Chair: Kazuhiro Iwasaki
               (For students 10000 YEN)

                       Tuesday, August 29

   8:30- 9:00  Registration / Poster Preparation

   9:00- 9:10  Announcement 10

   9:10-10:10  Session 5: Multi-level Logic Synthesis using EXORs.
                          Chair: Shin-Ichi Minato

          &  A new representation of strongly unspecified switching functions 
             and its application to multi-level AND/OR/EXOR synthesis,
             Marek A. Perkowski (Portland State University)
          &  Multi-level logic synthesis based on pseudo-Kronecker decision 
             diagrams and logical transformation,
             Tsutomu Sasao,
             Hiraku Hamachi,
             Seiji Wada and 
             Munehiro Matsuura (Kyushu Institute of Technology)
          &  Synthesis of multi-level circuits using EXOR-gates,
             B. Steinbach and 
             A. Wereszczynski (Freiberg University)
          &  Multiple domain logic synthesis,
             U. Kebschull,
             J. Bullmann (Forschungszentrum Informatik),
             E. Schubert and 
             W. Rosenstiel (University of Tubingen)
          &  Unified decision diagrams: a representation for 
             mixed AND-OR/EXOR combinational networks,
             Tomasz Kozlowski,
             Erik L. Dagless (University of Bristol) and 
             Jonathan M. Saul (Oxford University)
          &  Minimization of switching functions for a multiple-level 
             EXOR realization,
             Gopal Lakhani (Texas Tech University)

  10:10-11:00  Break / Poster

  11:00-11:30  Session 6: Complexity.
                          Chair: Kiyoharu Hamaguchi          

          &  Note on the complexity of binary moment diagram representations,
             Reinhard Enders (Siemens AG)
          &  Complexity theoretical aspects of OFDDs,
             Beate Bolling,
             Martin Lobbing,
             Martin Sauerhoff and 
             Ingo Wegener (Univ. Dortmund)
          &  Satisfiability problems for ordered functional decision diagrams,
             Ralph Werchner,
             Thilo Harich,
             Rolf Drechsler (Johann Wolfgang Goethe-University) and 
             Bernd Becker (University of Freiburg)

  11:30-12:00  Poster

  12:00-13:00  Lunch

  13:00-14:00  Session 7: Optimization of FPRMs, KROs, and GRMs.
                          Chair: Christoph Meinel

          &  Exact minimization of fixed polarity Reed-Muller expressions 
             using multi-terminal EXOR ternary decision diagram,
             Tsutomu Sasao and 
             Fumitaka Izuhara (Kyushu Institute of Technology)
          &  Minimum polynominal implementation of systems of incompletely 
             specified Boolean functions,
             Arkadij Zakrevskij (Institute of Engineering Cybernetics)
          &  Approximate minimization of generalized Reed-Muller forms,
             Xiaoqiang Zeng, 
             Marek A. Perkowski and 
             Andisheh Sarabi (Portland State University)
          &  A new efficient algorithm for finding exact minimal generalized 
             partially-mixed-polarity Reed-Muller expansion,
             Xiaoqiang Zeng,
             Haomin Wu,
             Marek A. Perkowski and 
             Andisheh Sarabi (Portland State University)
          &  Exact minimization of Kronecker expressions for symmetric functions,
             Bernd Becker  (University of Freiburg) and 
             Rolf Drechsler (Johann Wolfgang Goethe-University)
          &  GRMIN: A heuristic minimization algorithm for generalized 
             Reed-Muller expression,
             Debatosh Debnath and 
             Tsutomu Sasao (Kyushu Institute of Technology)
             (poster only)
          &  Fixed polarity Reed-Muller expressions of symmetric Boolean 
             Valery P. Suprun (Beylorussian State University)

  14:00-14:30  Break / Poster

  14:30-15:20  Session 8: Polynomial Expansions.
                          Chair: Mark. A. Perkowski

          &  Quasi-arithmetic polynomial expansions for quaternary functions,
             Bogdan J. Falkowski and 
             Susanto Rahardja (Nanyang Technological University)
          &  Family of fast transforms for GF(2) orthogonal logic,
             Bogdan J. Falkowski and 
             Susanto Rahardja (Nanyang Technological University)
          &  New families of universal additive canonical forms of 
             switching functions,
             Marek A. Perkowski (Portland State University),
             Andisheh Sarabi (Viewlogic Systems, Inc.) and 
             F. Rudolf Beyl (Portland State University)
          &  Arithmetical canonical expansion of Boolean functions as 
             generalized Reed-Muller series,
             S. N. Yanushkevich (Technical University of Szczecin)
          &  Fast Reed-Muller spectrum computation using output probabilities,
             M. A. Thornton and 
             V. S. Nair (Southern Methodist University)

  15:20-15:50  Break / Poster

  15:50-16:30  Session 9: High-Speed and Testable Design.
                          Chair: Kiyoshi Furuya

          &  Design of highly parallel circuits using EXOR gates for 
             symmetrical logic operations,
             Masami Nakajima,
             Michitaka Kameyama (Tohoku University)
          &  State diagrams of elementary cellular automata with 
             arbitrary boundary conditions,
             Poh Yong Koh and 
             Kiyoshi Furuya (Chuo University)
          &  Self-testable circuits with single fault detection,
             Roustam Kh. Latypov (Kazan State University)
          &  Online self-checking FPGA structures based on 
             Reed-Muller networks,
             M. Riege and 
             W. Anheier (University of Bremen)

  16:30-17:00  Break / Poster

  18:00-20:00  PC Committee Meeting

Papers with * marks: 25 minutes presentation +5 minutes Q.A.
Other papers: 10 minutes presentation +poster