Guo-Jun Qi, Charu Aggarwal, et al.
IEEE TPAMI
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.
Guo-Jun Qi, Charu Aggarwal, et al.
IEEE TPAMI
Susan L. Spraragen
International Conference on Design and Emotion 2010
Pavel Klavík, A. Cristiano I. Malossi, et al.
Philos. Trans. R. Soc. A
Hannah Kim, Celia Cintas, et al.
IJCAI 2023