Proceedings

A Theory of Average-Case Compilability in Knowledge Representation

Download BibTeX Cite

Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence. Pages 455-459.

© 2003 International Joint Conferences on Artificial Intelligence

Abstract

Compilability is a fundamental property of knowledge representation formalisms which captures how succinctly information can be expressed. Although many results concerning compilability have been obtained, they are all "worst-case" results. We develop a theory of average-case compilability which allows for the formal comparison and classification of knowledge representation formalisms "on average."

  1. [Balcazar et al., 1995] J. L. Balcazar and J. Dfaz and J. Gabarr6. Structural Complexity I. Springer-Verlag, Berlin, 1995.
  2. [Cadoli et al., 2000a] Marco Cadoli, Francesco M. Donini, Paolo Liberatore, and Marco Schaerf. Preprocessing of intractable problems. Information and Computation, 176(2):89-120, 2000.
  3. [Cadoli et al., 1999] Marco Cadoli, Francesco M. Donini, Paolo Liberatore, and Marco Schaerf. The size of a revised knowledge base. Artificial Intelligence, 115(1), 25~64.
  4. [Cadoli et al., 2000b] Marco Cadoli, Francesco M . Donini, Paolo Liberatore, and Marco Schaerf. Space Efficiency of Propositional Knowledge Representation Formalisms. Journal of Artificial Intelligence Research, 13:1-31, 2000.
  5. [Cadoli et al., 1997] Marco Cadoli, Francesco M. Donini, Marco Schaerf, and Riccardo Silvestri. On Compact Rep- resentations of Propositional Circumscription. In Theoret- ical Computer Science, 182:183-202.
  6. [Cadoli et al., 1996] Marco Cadoli, Francesco M. Donini, and Marco Schaerf. Is Intractability of Non-Monotonic Reasoning a Real Drawback? Artificial Intelligence, 88:215-251.
  7. [Gogic et al., 1995] Goran Gogic, Henry Kautz, Christos Pa- padimitriou, and Bart Selman. The Comparative Linguis- tics of Knowledge Representation. In Proceedings of the 14th International Joint Conference on Artificial Intelli- gence, pages 862-869, Montreal, Canada, 1995. IJCAI
  8. [Goldreich, 1997] Oded Goldreich. Notes on Levin's Theory of Average-Case Complexity. Electronic Colloquium on Computational Complexity (ECCC) 4(58): 1997.
  9. [Gurevich, 1991a] Yuri Gurevich. Average case complete- ness. Journal of Computer and System Sciences, 42:346- 398, 1991.
  10. [Gurevich, 1991b] Yuri Gurevich. Average case complexity. In Proceedings of the I 8th International Colloquium on Automata, Languages and Programming, volume 510 of Lecture Notes in Computer Science, Springer, pages 615- 628, 1991.
  11. [Gurevich, 1989] Yuri Gurevich. The challenger-solver game: variations on the theme of P =? NP. EATCS Bul- letin, pages 112-121, 1989.
  12. [lmpagliazzo, 1995] Russell Impagliazzo. A personal view of average-case complexity. In Proceedings of the lOth Conference on Structure in Complexity Theory, IEEE Computer Society Press, pages 134-147, 1995.
  13. [Johnson, 1984] David Johnson. The NP-completeness col- umn: an ongoing guide. Journal of Algorithms, 5:284-299, 1984.
  14. [Kautz et al., 1995] Henry Kautz, Michael Kearns, and Bart Selman. Horn approximations of empirical data. Artificial Intelligence, 75:129-145.
  15. [Khardon and Roth, 1996] Roni Khardon and Dan Roth. Reasoning with Models. Artificial Intelligence 87:187- 213, November 1996.
  16. [Levin, 1986] Leonid Levin. Average case complete prob- lems. SIAM Journal on Computing, 15:285-286, 1986.
  17. [Papadimitriou, 1996] Christos Papadimitriou. The Com- plexity of Knowledge Representation. In Proceedings of the Eleventh Annual IEEE Conference on Computational Complexity, pages 244-248, Philadelphia, Pennsylvania, May 1996.
  18. [Wang, 1997] Jie Wang. Average-case computational com- plexity theory. (L. Hemaspaandra and A. Selman, eds.), Complexity Theory Retrospective II, Springer-Verlag, pages 295-328, 1997.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards