Rangachari Anand, Kishan Mehrotra, et al.
IEEE Transactions on Neural Networks
In connection with the least fixed point operator the following question was raised: Suppose that a first-order formula P(P) is (semantically) monotone in a predicate symbol P on finite structures. Is P(P) necessarily equivalent on finite structures to a first-order formula with only positive occurrences of P? In this paper, this question is answered negatively. Moreover, the counterexample naturally gives a uniform sequence of constant-depth, polynomial-size, monotone Boolean circuits that is not equivalent to any (however nonuniform) sequence of constant-depth, polynomial-size, positive Boolean circuits. © 1987, ACM. All rights reserved.
Rangachari Anand, Kishan Mehrotra, et al.
IEEE Transactions on Neural Networks
Barry K. Rosen
SWAT 1972
Gaku Yamamoto, Hideki Tai, et al.
AAMAS 2008
Yi Zhou, Parikshit Ram, et al.
ICLR 2023