Premium
Expressiveness and tractability in knowledge representation and reasoning 1
Author(s) -
Levesque Hector J.,
Brachman Ronald J.
Publication year - 1987
Publication title -
computational intelligence
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.353
H-Index - 52
eISSN - 1467-8640
pISSN - 0824-7935
DOI - 10.1111/j.1467-8640.1987.tb00176.x
Subject(s) - rotation formalisms in three dimensions , expressive power , representation (politics) , computer science , limit (mathematics) , knowledge representation and reasoning , artificial intelligence , theoretical computer science , cognitive science , natural language processing , mathematics , psychology , mathematical analysis , geometry , politics , political science , law
A fundamental computational limit on automated reasoning and its effect on knowledge representation is examined. Basically, the problem is that it can be more difficult to reason correctly with one representational language than with another and, moreover, that this difficulty increases dramatically as the expressive power of the language increases. This leads to a tradeoff between the expressiveness of a representational language and its computational tractability. Here we show that this tradeoff can be seen to underlie the differences among a number of existing representational formalisms, in addition to motivating many of the current research issues in knowledge representation.