Departmental Colloquium
Martin C. Golumbic
University of Haifa
Read-Once Functions and Cographs Revisited
Abstract: Graph theory and its applications is an exciting mathematical discipline
which motivates the search for new algorithms, exact structures and
combinatorial properties. To illustrate this point, consider the
following simple question:
When can you factor a logic (Boolean) formula, into a (logically
equivalent) form in which each variable appears once and only once?
For example, the function f = ab + acd + ace satisfies this property since
it can be factored into the "read-once" expression f = a(b+c(d+e)).
However, the function h = ab + bc + cd does not satisfy the property.
Formally, a Boolean function f is called a read-once function if it has a
(logically equivalent) factored form in which each variable appears
exactly once, called a read-once expression for f.
Read-once functions have interesting combinatorial properties and often
arise in real circuit applications. They have also gained recent interest
in the field of computational learning theory.
In this talk, we will present the mathematical and computational aspects
of this problem. We will show several classical characterizations of
read-once functions which involve combinatorics, graph theory and
properties of positive (monotone) Boolean functions. We also present the
first polynomial time algorithm for recognizing and factoring read-once
functions. The algorithm is based on a theorem of Gurvich and on algorithms
for cograph recognition and a new efficient method for checking normality.
Finally, we raise a number of questions regarding the factoring certain
non-read-once functions. In particular, we are able to show that if the
co-occurrence graph of a positive Boolean function f is a tree, then the
function is read-twice. However, no characterization is known for general
read-twice functions.
(Joint work with Aviad Mintz and Udi Rotics)
Monday November 21, 2005 at 3:00 PM in SEO 636