SciDok

Eingang zum Volltext in SciDok

Lizenz

Report (Bericht) zugänglich unter
URN: urn:nbn:de:bsz:291-scidok-35508
URL: http://scidok.sulb.uni-saarland.de/volltexte/2011/3550/


A formal definition for the expressive power of knowledge representation languages

Baader, Franz

Quelle: (1990) Kaiserslautern ; Saarbrücken : DFKI, 1990
pdf-Format:
Dokument 1.pdf (13.490 KB)

Bookmark bei Connotea Bookmark bei del.icio.us
SWD-Schlagwörter: Künstliche Intelligenz , Wissensrepräsentationssprache
Institut: DFKI Deutsches Forschungszentrum für Künstliche Intelligenz
DDC-Sachgruppe: Informatik
Dokumentart: Report (Bericht)
Schriftenreihe: Research report / Deutsches Forschungszentrum für Künstliche Intelligenz [ISSN 0946-008x]
Bandnummer: 90-05
Sprache: Englisch
Erstellungsjahr: 1990
Publikationsdatum: 04.03.2011
Kurzfassung auf Englisch: 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.
Lizenz: Standard-Veröffentlichungsvertrag

Home | Impressum | Über SciDok | Policy | Kontakt | Datenschutzerklärung | English