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)
|
Dr.
Martin Charles Golumbic is Professor of Computer Science and Director of
the Caesarea Edmond Benjamin de Rothschild Institute for Interdisciplinary Applications of Computer Science at the University of
Haifa. He is the founding editor-in-chief of the series “Annals of
Mathematics and Artificial Intelligence” and is or has been a member of
the editorial boards of several journals including “Discrete Applied
Mathematics”, “Constraints” and “AI Communications”. |