An improvement on the complexity of factoring read-once Boolean functions

详细信息    查看全文

• 作者：Martin Charles Golumbic ; Aviad Mintz ; Udi Rotics
• 关键词：Read-once functions ; Logic ; Boolean functions ; Cographs
• 刊名：Discrete Applied Mathematics
• 出版年：2008
• 出版时间：28 May 2008
• 年：2008
• 卷：156
• 期：10
• 页码：1633-1636
• 全文大小：123 K

文摘

Read-once functions have gained recent, renewed interest in the fields of theory and algorithms of Boolean functions, computational learning theory and logic design and verification. In an earlier paper [M.C. Golumbic, A. Mintz, U. Rotics, Factoring and recognition of read-once functions using cographs and normality, and the readability of functions associated with partial k-trees, Discrete Appl. Math. 154 (2006) 1465–1677], we presented the first polynomial-time algorithm for recognizing and factoring read-once functions, 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-occurrence graph is P₄-free.