Read-Once Functions Revisited and the Readability Number of a Boolean Function

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.