Excursion to Mount Saint Helen's.
Below find the contents of the Second Symposium.

Our special interest is in practical applications of logic synthesis methods outside circuit design.

PLACE: Room 138, Portland Center for Advanced Technology.
DATE: Tuesday, August 17, 1999.
AUDIENCE: Everybody is invited.
The goal of the symposium is to discuss new research in the area of Boolean and Multiple-Valued Logic with applications to VLSI circuit design, Machine Learning, Data Mining and Robotics.

The first lecture will introduce new Information relationships and measures that can be used to create efficient heuristic algorithms for functional decomposition, functional composition, minimal support set and other combinatorial problems in which certain relations on subsets of variables defining the problem are given.

The second lecture will discuss Boolean Equation and Bi-Decomposition, two general-purpose techniques that can be used in design of finite state machines and combinational logic.

The third lecture will discuss new approaches to the decomposition/composition of state machines and Boolean functions.

The fourth meeting will be a demo of visual software for state machine description (declarative), state assignment and realization in logic, including software for lattice-based design of FPGAs and cellular logic, an example of "layout-driven logic synthesis".

The next lecture will present new ideas about designing software and hardware for learning. Rather than using only Genetic Algorithm, we propose to use a variety of logic-based methods which give the explanation of concepts learned and are all based on Occam Razor Principle of Machine Learning.

Panel discussion will discuss topics of collaboration and new research ideas.


  1. TUESDAY, 11:15-12:15,
    Marek Perkowski - Welcome and Goals.

    Lech Jozwiak, Associate Professor, Eindhoven University of Technology, Faculty of Electrical Engineering, Eindhoven, The Netherlands, ``Logic Analysis and Synthesis with Information Relationships and Information Relationship Measures,''

  2. TUESDAY, 12:30 - 1:30,

  3. TUESDAY, 1:45 - 2:45,
    Bernd Steinbach, Dr.Ing-habil, Chair of Institute fuer Informatik, TU Bergakademie Freiberg, Germany, ``Modelling and Solving of Problems by Boolean Equation or Boolean Differential Equations,''

  4. TUESDAY, 3:00 - 4:00,
    Lech Jozwiak, Associate Professor, Eindhoven University of Technology, Faculty of Electrical Engineering, Eindhoven, The Netherlands, ``General Decomposition of Sequential Machines and Discrete Functions,''

  5. TUESDAY, 4:00 - 5:00,
    Alan Mishchenko, Visiting Assistant Professor, Glushkov Institute of Cybernetics, Ukraine, ``Integrated System for Logic Synthesis, Data Mining and Robotics,'' Software demonstration: DUAL, TRACE, SYNTHA, LOTUS and robot.

  6. TUESDAY, 5:15 - 6:00,
    Marek Perkowski, Professor, PSU, ``Learning Hardware rather than Evolving Hardware''

  7. TUESDAY, 6:15 - 7:00,
    PANEL DISCUSSION: ``Plans for collaboration,'' - Marek Perkowski.

    1. Book on Multiple-Valued Logic:

        The plans are for this book to be published in two years. The book will describe only those aspects of mv-logic that are of interest to hardware and software engineers, it will be practical and simple, with many examples and emphasis on practical applications in future technologies. Modern binary techniques will be also used to demonstrate special cases.

        Several authors already volunteered to write its chapters. We will discuss the scope and the goals of the book. The emphasis will be on low power and issues that dominate chip design about year 2020 when the current technology will reach its limits.
      1. Introduction, goals.
      2. CHAPTER 1: Mathematical fundamentals. Functions, relations, function and relation sets, finite state machines, non-deterministic state machines, types of functions, classes, properties: symmetric, unate. Counting. Statical and dynamical theories.
      3. CHAPTER 2: Representation Methods and Data Structures: Cube Calculus, Spectra, Decision Diagrams, Labeled Rough Partitions, Bidirectional Decision Diagrams. Applications in Analysis, Synthesis, Test and Verification. Characteristic Functions and Implicit Methods (Craig Files, Marek Perkowski, Alan Mishchenko and Stan Grygiel).
      4. CHAPTER 3: Examples of practical applications of Multiple-Valued logic in various areas. Knowledge Discovery from Data Mining, Machine Learning and Pattern Recognition, Robotics, Circuit Design. Algorithms. Multi-valued System Theory.
      5. CHAPTER 4: New Information-Based Measures and Relationships and their applications (Jozwiak).
      6. CHAPTER 5: Differential Methods and their applications (Yanushkevich).
      7. CHAPTER 6: Functionally complete systems. Irredundant systems and Two-level synthesis: MIN/MAX, MIN-MODSUM, Galois Fields, Boolean Rings.
      8. CHAPTER 7: Information-Theory based measures and methods (Yanushkevich).
      9. CHAPTER 8: Decomposition and Bi-Decomposition of Multiple-Valued Functions, Relations and Sets of Relations (Steinbach and Perkowski).
      10. CHAPTER 9: Decomposition and Composition of Multiple-Valued Functions. (Jozwiak). (Steinbach and Perkowski).
      11. CHAPTER 10: Decomposition, Composition and Encoding of State Machines. (Jozwiak and Mishchenko).
      12. CHAPTER 11: Spectral Methods (Falkowski and Moraga).
      13. CHAPTER 12: Testing and Design for Test (Shmerko, Perkowski, Kalay).
      14. CHAPTER 13: Realization technologies for Multiple-Valued Logic: CMOS, bi-CMOS, IIL, current, Josephson Junction, quantum.
      15. CHAPTER 14: Multiple-Valued Knowledge-Based Systems of the Future. (Kameyama, Hanyu, Higuchi).

    2. Unified Software Package for logic synthesis.
        We propose a package based on Functional decomposition of relations and state machine acquisition from temporal constraints and declarative equations.

    3. Learning Robots and Animated Puppets controlled by FPGA engines.
        Our Intel's grant covers undergraduate robotics laboratory. We will present our ideas how to link the mechanical and electrical robotics mechanisms that we have built with high level learning software.

    4. Unified Software Package for Data Mining based on MV decomposition and state machine acquisition.
        We will discuss ideas of using our existing and possibly other software for Data Mining.

    5. Quantum Logic.
        We will briefly present Quantum Logic and its links with Linearly Independent Logic as a future research area.


Logic Analysis and Synthesis with
Information Relationships and Information Relationship Measures

Lech Józwiak
Eindhoven University of Technology
Faculty of Electrical Engineering
P.O. Box 513, EH 10.25
5600 MB Eindhoven, The Netherlands


In this presentation, the theory of information relationships and
relationship measures is considered and its application to logic
analysis and synthesis is discussed.
The information relationships and measures can be applied for analysis
and estimation of information and information interrelationships in many
fields of modern engineering and science, including logic and
architecture synthesis for VLSI systems, pattern analysis, knowledge
discovery, machine learning, decision systems, data bases, data mining
etc. They can be applied for both the binary as well as the
multiple-valued and symbolic systems. They enable designers and tools to
analyze various relationships between the information streams of the
considered systems, and provide them with data necessary for effective
and efficient decision-making. Results of the relationship analysis make
it possible to discover the nature of the considered system or to decide
its structure in order to satisfy given design constraints or optimize
certain objectives.

The theory of information relationships and measures makes operational
the famous theory of partitions and set systems of Hartmanis. Partitions
and set systems are used for various purposes in logic synthesis,
pattern analysis, knowledge discovery, machine learning, decision
systems, databases, data mining, and other fields. Partitions and set
systems enable us to model information streams. The information
relationship measures enable us to analyze the relationships between the
modeled information streams. The theory of partitions and set systems
and the theory of information relationships and measures form just
together an information modeling and analysis apparatus that is of
primary importance for analysis and synthesis of discrete information
systems, and in particular for logic design.

This presentation shows how to apply the relationships and measures to
logic design when using as examples important logic synthesis problems,
such as: input support minimization, parallel decomposition and serial
functional decomposition. The application examples and experimental
results presented demonstrate the high potential of the information
relationships and measures in solving logic analysis and synthesis


General Decomposition of
Sequential Machines and Discrete Functions

Lech Jozwiak
Eindhoven University of Technology
Faculty of Electrical Engineering
P.O. Box 513, EH 10.25
5600 MB Eindhoven, The Netherlands


Modern microelectronic technology gives us opportunities to build very
complex digital circuits and systems at a relatively low cost and
provides a huge diversity of logic building blocks. However, the
opportunities cannot be fully exploited, because of weaknesses of the
traditional logic synthesis methods. Particularly in the case of
(C)PLDs, look-up table FPGAs  and complex CMOS gates, the constraints
are imposed not on the function type a certain block can implement, but
on various building block structural parameters (e.g. the number of
inputs, outputs, product terms, flip-flops in a building block or the
number of serial and parallel transistors in a gate) and on
interconnections between the building blocks. A block is able to
implement any function with limited dimensions. On the other hand, the
traditional logic synthesis methods do not consider hard structural
constraints. In principle, they are devoted to only some very special
cases of possible implementation structures involving some minimal
functionally complete systems of logic gates (e.g. AND+OR+NOT, AND+EXOR,
MUX). They require a post synthesis technology mapping for another
implementation structures. If the actual synthesis target strongly
differs from these minimal systems, e.g. involves a lot of complex
gates, look-up table FPGAs or (C)PLDs, the library based technology
mapping is impossible and any technology mapping cannot guarantee a good
result if the initial synthesis was performed without close relation to
the actual target.

Therefore, there is presently much research in the field of general
(functional) decomposition of sequential machines and discrete (
Boolean) functions related to VLSI design automation. The most promising
recent approaches in pattern analysis, knowledge discovery, machine
learning, decision systems, data bases, data mining etc. are also based
on functional decomposition. Our works in the field of general
decomposition focused on decomposition theory and heuristic search
algorithms for decomposition. Among others, I developed the theory of
general decomposition of sequential machines and explained how the
theory can be used for the synthesis of sequential and combinational
circuits. The central point of this theory is the constructive theorem
on the existence of general decomposition. It delivers a generator of
correct circuit structures. For large circuits however, the number of
possible decompositions is so great that it becomes necessary to
construct only the most promising decompositions, using the general
decomposition theorem, or its special cases, together with the
appropriate heuristic evaluation functions and selection mechanisms.
These evaluation and selection mechanisms must limit the search space to
a manageable size while keeping high-quality solutions in the limited
space. In particular, the analysis and evaluation of relationships
between information in various information streams of a specified
function, relation or sequential machine is here of primary importance.
The fundamental analysis apparatus for this aim: the theory of
information relationships and measures will be considered in a separate
presentation. This presentation will focus on the theory of general
decomposition, heuristic search algorithms and benchmark results.


Modeling and Solving of Boolean Problems by Boolean Equations or Boolean Differential Equations

Bernd Steinbach
Freiberg University of  Mining and Technology
Institute of Computer Sience
Bernhard-von-Cotta-Str. 1
D-09596 Freiberg, Germany


This presentation starts  with some basic definitions about Boolean space, 
Boolean function, Boolean equation and their solution. Next the relationships
between a single Boolean equation and a system of Boolean equations will be discussed. 

Using an well understanding example of a criminal case, I demonstrate the modeling 
of a difficult problem by a system of Boolean equations. The inspector should find 1
of 37,778,931,862,957,161,709,568 possible solutions. I demonstrate the real time solution
of this problem using the program system XBOOLE. Note, one year has
31,563,000,000,000,000 nanoseconds, so we need more than 1 Million years, 
if we spend only 1 nanosecond to decide about over each possible solution!!! 
(I will show you the calculation of the solution a little bit faster.)

More general the problem may be characterized by dynamic behavior. 
In this case we need the Boolean Differential Calculus for modeling. 
I introduce the differential of a Boolean variable, the differential of
a Boolean function, some other Boolean differential operations and
Boolean derivation operations. Using all these elements in an Boolean
equation we get an more general Boolean differential equation. 

The simplest Boolean differential equation is a so called graph equation, 
in which Boolean variables and Boolean differentials of a Boolean variables
combined by Boolean operation. I demonstrate the modeling of the well
known "Ferryman - Wolf - Goat - Cabbage" problem and
calculation of the solution using the program system XBOOLE.

The presentation finished with and overview about general Boolean differential equations.
I emphasize the new type of solution. On an example of the EXOR-bi-decomposition
I illustrate the algorithm of class separation. By means of this algorithm
the set of all EXOR-bi-decomposable function may by calculated.


Marek Perkowski.
``Learning Hardware rather than Evolving Hardware''

Evolvable Hardware is Genetic Algorithm (GA) plus reconfigurable hardware.
One may ask: "Why Genetic Algorithm"?
Based on our experience, we question the usefulness of GA
as a sole learning method to reconfigure binary FPGAs.
Instead, we propose the "Learning Hardware" approach, which consists of creating a
sequential network based on feedback from the environment (for instance,
positive and negative examples from the trainer), and 
realizing this network in an array of Field Programmable Gate Arrays (FPGAs).

Here we advocate the approach to Learning Hardware
based on Induction of State Machines from Temporal Logic Constraints.
The method involves training on examples, constraints solving,
determinization, FSM minimization, structural mapping, 
functional decomposition of multi-valued logic functions and relations, and FPGA mapping.
Thus learning occurs on the level of constraints acquisition
and functional decomposition rather than on the low level of programming binary switches.
Ours is an Occam's Razor learning that allows for generalization and discovery.

Our software algorithms require fast operations on complex logic
expressions and solving NP-complete problems such as satisfiability.
They should be realized in hardware to obtain the necessary speed-ups.
Using a fast prototyping tool, the DEC-PERLE-1 board based on an array of Xilinx FPGAs,
we are developing software/configware processors that accelerate the acquisition, synthesis,
and optimization of Reactive State Machines.