×

Expressiveness and tractability in knowledge representation and reasoning. (English) Zbl 1341.68228

Lakemeyer, Gerhard (ed.) et al., Knowing, reasoning, and acting. Essays in honour of Hector J. Levesque. London: College Publications (ISBN 978-1-84890-044-8/hbk). Tributes 16, 11-26 (2011).
Summary: 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.
Editorial remark: Reprint of [the authors, Comput. Intell. 3, No. 2, 78–93 (1987)].
For the entire collection see [Zbl 1246.68046].

MSC:

68T30 Knowledge representation
68T27 Logic in artificial intelligence
PDFBibTeX XMLCite