Read-Once Functions Revisited and the Readability Number of a Boolean Function |
| |
| Institution: | 1. Institute of Medical Systems Biology, Ulm University, Albert-Einstein-Allee 11, 89081 Ulm, Germany;2. Institute of Biochemistry and Molecular Biology, Ulm University, Albert-Einstein-Allee 11, 89081 Ulm, Germany;1. Department of Mathematics, Faculty of Arts and Sciences, Ondokuz Mayis University, 55139 Samsun, Turkey;2. Dep. of Physics, Faculty of Applied Sciences, Palestine Technical University, Tulkarm, Palestine;3. Dep. of Applied Computing, Faculty of Applied Sciences, Palestine Technical University, Tulkarm, Palestine;1. Departamento de Ingeniería Informática, Universidad de Concepción, Edmundo Larenas 219, Concepción, Chile;2. Departamento de Ingeniería Industrial, Universidad de Concepción, Edmundo Larenas 219, Concepción, Chile;2. Laboratoire I3S, UMR CNRS 7271 & Université de Nice-Sophia Antipolis, 2000 route des Lucioles, 06903 Sophia Antipolis, France |
| |
| Abstract: | In this paper, we present the first polynomial time algorithm for recognizing and factoring read-once functions. The algorithm is based on algorithms for cograph recognition and a new efficient method for checking normality. Its correctness is based on a classical characterization theorem of Gurvich which states that a positive Boolean function is read-once if and only if it is normal and its co-occurrance graph is P4-free.We also investigate the problem of factoring certain non-read-once functions. In particular, we show that if the co-occurrence graph of a positive Boolean function f is a tree, then the function is read-twice. We then extend this further proving that if f is normal and its corresponding graph is a partial k-tree, then f is a read 2k function and a read 2k formula for F for f can be obtained in polynomial time. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
