Copyright Statement: This is an open access article licensed under a Creative Commons Attribution 4.0 International License, which permits unrestricted use, distribution, and reproduction in any medium, even commercially as long as the original work is properly cited.
Digital Object Identifier (DOI) : 10.14569/IJARAI.2014.031205
Article Published in International Journal of Advanced Research in Artificial Intelligence(IJARAI), Volume 3 Issue 12, 2014.
Abstract: The circumscription of a propositional formula T may not be representable in polynomial space, unless the polynomial hierarchy collapses. This depends on the specific formula T, as some can be circumscribed in little space and others cannot. The problem considered in this article is whether this happens for a given formula or not. In particular, the complexity of deciding whether CIRC(T) is equivalent to a formula of size bounded by k is studied. This theoretical question is relevant as circumscription has applications in temporal logics, diagnosis, default logic and belief revision.
Paolo Liberatore, “Checking the Size of Circumscribed Formulae” International Journal of Advanced Research in Artificial Intelligence(IJARAI), 3(12), 2014. http://dx.doi.org/10.14569/IJARAI.2014.031205