Expressiveness against tractability
How much can a knowledge language say before reasoning with it becomes too slow, or impossible to complete?
- issue
- reasoning
- status
- reopened
- steps
- 10, 1975–2023
- threads
- all problem threads
Once semantic networks were given formal meaning, researchers found that every extra feature in a representation language could make reasoning dramatically harder. Description logics mapped the trade-off precisely, and OWL was built on them, first with three sublanguages and then with OWL 2's tractable profiles. Validation with SHACL and statistical methods such as knowledge-graph embeddings and language models now sidestep sound reasoning altogether.
Lineage
-
1975
What's in a Link: Foundations for Semantic Networks
Shows that the links in semantic networks had no agreed meaning, mixing up a class with its members and a definition with an assertion, and calls for a formal semantics. [src]
-
Apr 1985
An Overview of the KL-ONE Knowledge Representation System
KL-ONE: defined concepts and an automatic classifier that places each concept in a subsumption hierarchy, the first system based on what became description logics. [src]
-
Feb 1987
Expressiveness and Tractability in Knowledge Representation and Reasoning
Reasoning correctly gets dramatically harder as a language's expressive power grows. This trade-off underlies the differences between existing representation formalisms. [src]
- 2001
-
Dec 2003
From SHIQ and RDF to OWL: The Making of a Web Ontology Language
The design history of OWL, traced from the description logic SHIQ and from RDF. [src]
- 10 Feb 2004
- 27 Oct 2009
-
2013
Translating Embeddings for Modeling Multi-relational Data
Represents entities as vectors and relations as translations between them, so missing facts are predicted from patterns rather than derived by logic. [src]
- 20 Jul 2017
-
14 Jun 2023
Unifying Large Language Models and Knowledge Graphs: A Roadmap
Three ways to combine language models and knowledge graphs: graphs that ground language models, language models that build graphs, and the two working together. [src]
Open now
Under each question, the answers people have put forward or built. The catalogue gives no odds on them.
- Can systems built on learned models keep any of the guarantees that sound reasoning gives?
[src1][src2]
Embeddings and language models predict facts rather than derive them; the 2023 roadmap sets out ways to combine them with knowledge graphs.
- Learned models propose and a sound reasoner checks. Unifying Large Language Models and Knowledge Graphs: A Roadmap
The 2023 roadmap describes systems where knowledge graphs and reasoning constrain and verify what language models produce.[src]
- Learned models propose and a sound reasoner checks. Unifying Large Language Models and Knowledge Graphs: A Roadmap
- How far can tractable profiles stretch as ontologies grow to hundreds of thousands of classes?
[src]
OWL 2 EL was designed for ontologies with very large numbers of classes and properties, such as those in medicine.
Forces
Pressures that push this problem one way or another, as their sources argue them. All forces
- General methods that scale keep winning
Suggests that systems which predict at scale may displace those which derive with guarantees, whatever the cost to soundness.[src]
- Language models need knowledge to check against
Creates demand for reasoners that can check what learned models produce.[src]
How to contribute
-
International Workshop on Description Logics
conference
Annual workshop of the description logic community; the 39th ran in Lisbon in July 2026 alongside KR 2026. Calls for papers go out on the DL mailing list. [src1][src2]
checked 21 Oct 2026 -
Protégé
repository
· Protégé
Open-source ontology editor with built-in OWL reasoners, developed openly on GitHub. [src]
checked 21 Oct 2026