Levesque, Hector J.; Brachman, Ronald J. 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]. Cited in 20 Documents MSC: 68T30 Knowledge representation 68T27 Logic in artificial intelligence Keywords:knowledge representation; description subsumption; complexity of reasoning; first-order logic; frames; semantic networks; databases PDFBibTeX XMLCite \textit{H. J. Levesque} and \textit{R. J. Brachman}, Tributes 16, 11--26 (2011; Zbl 1341.68228)