Facebook pixel tracking

The Science and Information (SAI) Organization publishes open-access peer-reviewed journals in computer science and artificial intelligence.

Contact Info
Email info@thesai.org
Website thesai.org
Follow Us
Contact Info
Email info@thesai.org
Follow Us
Research Article | Open Access |

Checking the Size of Circumscribed Formulae

Author 1: Paolo Liberatore
International Journal of Advanced Research in Artificial Intelligence (IJARAI) · Vol. 3, No. 12 · Published 2014

DOI: 10.14569/IJARAI.2014.031205

Download PDF Cite

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.

Keywords

Circumscription computational complexity belief revision.

How to Cite this Article

Liberatore, P. (2014). Checking the Size of Circumscribed Formulae. International Journal of Advanced Research in Artificial Intelligence, 3(12). https://doi.org/10.14569/IJARAI.2014.031205

Liberatore, Paolo. "Checking the Size of Circumscribed Formulae." International Journal of Advanced Research in Artificial Intelligence, vol. 3, no. 12, 2014, https://doi.org/10.14569/IJARAI.2014.031205.

@article{Liberatore2014,
  title     = {Checking the Size of Circumscribed Formulae},
  journal   = {International Journal of Advanced Research in Artificial Intelligence},
  volume    = {3},
  number    = {12},
  year      = {2014},
  publisher = {The Science and Information Organization},
  author    = {Paolo Liberatore},
  doi       = {10.14569/IJARAI.2014.031205},
  url       = {https://doi.org/10.14569/IJARAI.2014.031205}
}

Open Access — licensed under a Creative Commons Attribution 4.0 International License. Unrestricted use, distribution, and reproduction in any medium, even commercially, as long as the original work is properly cited.

Back to Issue
IJARAI Journal Cover