Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen: doi:10.22028/D291-24777
Titel: A formal definition for the expressive power of knowledge representation languages
Verfasser: Baader, Franz
Sprache: Englisch
Erscheinungsjahr: 1990
Quelle: Kaiserslautern ; Saarbrücken : DFKI, 1990
SWD-Schlagwörter: Künstliche Intelligenz
Wissensrepräsentationssprache
DDC-Sachgruppe: 004 Informatik
Dokumentart : Report (Bericht)
Kurzfassung: The notions "expressive power" or "expressiveness" of knowledge representation languages (KR-languages) can be found in most papers on knowledge representation; but these terms are usually just used in an intuitive sense. The papers contain only informal descriptions of what is meant by expressiveness. There are several reasons which speak in favour of a formal definition of expressiveness: For example, if we want to show that certain expressions in one language cannot be expressed in another language, we need a strict formalism which can be used in mathematical proofs. Though we shall only consider KL-ONE-based KR-language in our motivation and in the examples, the definition of expressive power which will be given in this paper can be used for all KR-languages with model-theoretic semantics. This definition will shed a new light on the tradeoff between expressiveness of a representation language and its computational tractability. There are KR-languages with identical expressive power, but different complexity results for reasoning. Sometimes, the tradeoff lies between convenience and computational tractability. The paper contains several examples which demonstrate how the definition of expressive power can be used in positive proofs -- that is, proofs where it is shown that one language can be expressed by another language -- as well as for negative proofs -- which show that a given language cannot be expressed by the other language.
Link zu diesem Datensatz: urn:nbn:de:bsz:291-scidok-35508
hdl:20.500.11880/24833
http://dx.doi.org/10.22028/D291-24777
Schriftenreihe: Research report / Deutsches Forschungszentrum für Künstliche Intelligenz [ISSN 0946-008x]
Band: 90-05
SciDok-Publikation: 4-Mär-2011
Fakultät: Sonstige Einrichtungen
Fachrichtung: SE - DFKI Deutsches Forschungszentrum für Künstliche Intelligenz
Fakultät / Institution:SE - Sonstige Einrichtungen

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat 
RR_90_05.pdf13,49 MBAdobe PDFÖffnen/Anzeigen


Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.