On compact representations of propositional circumscription
| Author(s) : | Marco Schaerf Francesco M. Donini Marco Cadoli, |
| Publisher : | N/A |
| Publication Date : | 1995 |
| ISSN : | N/A |
| Abstract : | Abstract. We prove that-- unless the polynomial hierarchy collapses at the second level-- the size of a purely propositional representation of the circumscription CIRC(T) of a propositional formula T grows faster than any polynomial as the size of T increases. We then analyze the significance of this result in the related field of closed-world reasoning. Appeared on the Proceedings of the, |