Reasoning

What follows from it?

tension: Expressiveness against tractability: richer logics say more but cost more to compute, or cannot be computed at all.
also: Semantics, Meaning, Inference, Logic
scheme: design issues

Threads (4)

Long-running problems under this issue, told step by step. All threads.

Expressiveness against tractability 1975–2023 reopened 10 steps
How much can a knowledge language say before reasoning with it becomes too slow, or impossible to complete?
Hand-built meaning or learned meaning 1959–2024 open 11 steps
Do machines get meaning from knowledge people write down, or from patterns in large amounts of data?
Same thing, many names 2004–2026 open 6 steps
When two datasets name the same thing, how do we say so without claiming more than we mean?
Unknown or false? 1978–2026 largely settled 8 steps
When a fact is missing, is it unknown or false, and how do you check data in a world that assumes it is merely unknown?

Who answered it

This issue's row of the map: which traditions' works mainly answer it, and the earliest from each.

Works on this issue by tradition
tradition	works	earliest
Hypertext
Knowledge representation	17	Programs with Common Sense 1959
Databases
Machine learning	10	The Unreasonable Effectiveness of Data 2009
Web standards	5	DAML 1999
Search	4	The Semantic Web, Syllogism, and Worldview 2003
Social web
Open knowledge
Decentralized web
Libraries, archives and museums
Life sciences
Media
Geospatial	2	Tobler's first law of geography 1970
Commerce and supply chain
Government and law
Finance
Industry and engineering

5 of 17 traditions have taken up this question as a work's main issue; a work in several traditions counts in each. Same counts as the full map.

Timeline

Works on this question, its main or a secondary one, each shown once in date order; filter by tradition to follow one community. Bars run from start to end where both are known; marks people, projects and organizations still active. 8 entries have no date and are not shown. Hover over or focus an entry to draw its links. Scroll sideways, or use the decades above.

Lineage (27)

Works whose main question this is, by type, oldest first.

Concepts 5

Tobler's first law of geography 1970 concept principle
'Everything is related to everything else, but near things are more related than distant things': Waldo Tobler's 1970 principle, which underlies spatial interpolation and much of geographic reasoning.
Description logic concept formalism
Family of decidable logics for describing concepts and their relations; the formal basis of OWL.
Entailment and inference concept formalism
Deriving facts that follow from stated ones plus a schema or ontology, for example that a member of a subclass is also a member of its superclass.
Large language model concept technique
Neural language model trained on very large text collections; since the early 2020s the main way software works with unstructured text.
Neuro-symbolic AI concept technique
AI that combines neural networks with symbolic knowledge such as rules and knowledge graphs; it drew new attention in the 2020s as a way to ground large language models.

Writings 17

Programs with Common Sense 1959 writing ★ seminal vision
John McCarthy's 1959 paper proposing the 'advice taker', a program that would decide what to do by deducing it from facts and rules stated in formal logic; the founding statement of logic-based knowledge representation.
Semantic Information Processing 1968 writing
Collection of early AI research on meaning and language, edited by Marvin Minsky.
A Computer Movie Simulating Urban Growth in the Detroit Region 1970 writing ★ seminal principle
1970 paper by Waldo Tobler in Economic Geography, a computer animation of Detroit's growth, in which he states the first law of geography.
What's in a Link: Foundations for Semantic Networks 1975 writing ★ seminal debate
William Woods's 1975 critique showing that the links in semantic networks had no agreed meaning, mixing up, for example, a class with its members and a definition with an assertion; it set the agenda for giving networks a formal semantics.
An Overview of the KL-ONE Knowledge Representation System 1985 writing ★ seminal formalism
Brachman and Schmolze's 1985 account of KL-ONE, a frame-based system with defined concepts and an automatic classifier that places each concept in a subsumption hierarchy; KL-ONE was the first knowledge representation system based on what became description logics.
Expressiveness and Tractability in Knowledge Representation and Reasoning 1987 writing ★ seminal principle
Levesque and Brachman's 1987 paper showing that reasoning gets dramatically harder as a representation language gets more expressive, and that this trade-off underlies the differences between existing representation formalisms.
Building Large Knowledge-Based Systems 1990 writing
Book by Doug Lenat and R.V. Guha on the representation and inference methods of the Cyc project.
The Semantic Web, Syllogism, and Worldview 2003 writing ★ seminal debate
Clay Shirky's essay arguing that the Semantic Web's reliance on syllogistic logic fails on real-world, context-dependent data.
From SHIQ and RDF to OWL: The Making of a Web Ontology Language 2003 writing ★ seminal
Design history of OWL by Horrocks, Patel-Schneider and van Harmelen, tracing it from description logics and RDF.
The Unreasonable Effectiveness of Data 2009 writing ★ seminal debate
Halevy, Norvig and Pereira's 2009 essay arguing that simple models trained on very large amounts of web data beat elaborate hand-built models, and that meaning is better learned from use at scale than specified in advance.
ImageNet Classification with Deep Convolutional Neural Networks 2012 writing ★ seminal technique
2012 NIPS paper by Alex Krizhevsky, Ilya Sutskever and Geoffrey Hinton whose deep network, trained on GPUs, won the ImageNet image-recognition contest by a wide margin and turned machine learning toward deep learning.
Translating Embeddings for Modeling Multi-relational Data 2013 writing ★ seminal technique
2013 NIPS paper introducing TransE, which represents each entity in a knowledge graph as a vector and each relation as a translation between vectors, so that missing facts can be predicted; the starting point of knowledge-graph embeddings.
Efficient Estimation of Word Representations in Vector Space 2013 writing ★ seminal technique
2013 paper by Tomas Mikolov, Kai Chen, Greg Corrado and Jeffrey Dean introducing word2vec: vectors learned from which words occur together, in which relations such as king to queen show up as directions.
Knowledge Vault: A Web-Scale Approach to Probabilistic Knowledge Fusion 2014 writing
2014 KDD paper by Xin Luna Dong and eight Google colleagues describing a knowledge base built by machine: facts extracted from text, tables and page structure across the Web, combined with existing knowledge bases and given probabilities of being true.
Attention Is All You Need 2017 writing ★ seminal technique
2017 paper by Ashish Vaswani and seven Google colleagues introducing the transformer, a network built on attention that became the basis of large language models.
BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding 2018 writing technique
2018 paper by Jacob Devlin, Ming-Wei Chang, Kenton Lee and Kristina Toutanova: a transformer pre-trained on large amounts of text that set new results on many language tasks; Google applied it to Search in 2019.
Unifying Large Language Models and Knowledge Graphs: A Roadmap 2023 writing vision
Survey proposing three ways to combine language models and knowledge graphs: KG-enhanced LLMs, LLM-augmented KGs, and the two working together.

Standards 3

DAML+OIL 2001 standard
Ontology language formed in 2001 by merging the American DAML with the European OIL; a thin layer over RDF Schema with description-logic semantics, and the direct basis of OWL.
OWL 2004 standard ★ seminal
W3C language for writing ontologies on the Web, based on description logics. OWL 2 followed in 2009.
OWL 2 2009 standard
Second version of OWL, adding profiles such as OWL 2 EL, QL and RL for tractable reasoning; a W3C Recommendation since October 2009.

Projects 2

Cyc 1984 project ★ seminal
Long-running project to hand-encode common-sense knowledge as a logical knowledge base, started at MCC and continued by Cycorp.
DAML 1999 project
DARPA research programme started in 1999 by Jim Hendler to create machine-readable representations for the Web; its RDF-based DAML language fed directly into OWL.

Also bears on this (21)

Concepts 6

Semantic network 1956 concept formalism
Graph of concepts joined by labelled relations, used to represent meaning; first proposed by Richard Richens in 1956 and developed by Quillian and others in the 1960s.
Frames 1974 concept formalism
Knowledge structures of slots with default values describing stereotyped situations, proposed by Marvin Minsky in 1974.
Identity and co-reference concept debate
The problem of recognising when different names refer to the same thing. OWL's owl:sameAs states it, but used loosely across datasets it merges things that are only similar.
Ontology (information science) concept formalism
Formal description of the concepts in a domain and the relations between them, which software can use to reason about data.
Ontology spectrum concept
Scale of increasingly formal knowledge organization, from catalogues and glossaries through thesauri and taxonomies to logic-based ontologies, drawn to clarify the many things called 'ontologies'.
Open-world assumption concept principle
The rule that a fact missing from the data is unknown, not false. RDF and OWL assume it, unlike most databases.

Writings 8

Semantic Memory 1968 writing formalism
M. Ross Quillian's account of a memory model that stores word meanings as a network of linked concepts.
A Framework for Representing Knowledge 1974 writing ★ seminal formalism
Marvin Minsky's MIT AI Lab memo introducing frames: structures of slots with default values for stereotyped situations.
On Closed World Data Bases 1978 writing ★ seminal formalism
Raymond Reiter's 1978 paper formalizing the closed-world assumption: a database may treat any fact it cannot show to be true as false.
Ontology Matching 2007 writing technique
Book by Jérôme Euzenat and Pavel Shvaiko (2007; second edition 2013) on methods for finding correspondences between the terms of different ontologies, so that data described in one can be used with another.
Semantic Web for the Working Ontologist 2008 writing technique
Practitioner's guide by Dean Allemang and Jim Hendler to modelling with RDFS and OWL.
When owl:sameAs Isn't the Same: An Analysis of Identity in Linked Data 2010 writing ★ seminal
2010 ISWC paper showing that owl:sameAs links between Linked Data sets are often used to mean 'similar' or 'related' rather than strict identity, and proposing finer-grained alternatives.
Towards Making Systems Forget with Machine Unlearning 2015 writing
2015 IEEE Symposium on Security and Privacy paper by Yinzhi Cao and Junfeng Yang that named machine unlearning: removing the effect of particular training data from a learned model without retraining it from scratch.
sameAs.cc: The Closure of 500M owl:sameAs Statements 2018 writing technique
2018 ESWC paper that collected about 559 million owl:sameAs statements from a 2015 crawl of Linked Data, computed which names they make equivalent, and published the result with an error score for each link.

Standards 6

SHOE c. 1996 standard
Simple HTML Ontology Extensions: an early language for writing ontologies and annotating web pages with machine-readable claims, developed at the University of Maryland around 1996; among the first ontology languages made for the Web.
SNOMED CT 2002 standard
Logic-based clinical terminology of medical concepts and their relations, released in January 2002 and maintained by SNOMED International.
RDF Schema 2004 standard ★ seminal
W3C vocabulary for describing classes and properties of RDF data; the first schema language for RDF.
GeoSPARQL 2012 standard ★ seminal
OGC standard, version 1.0 from 2012 and 1.1 from January 2024, that adds a vocabulary for geometries to RDF and spatial functions and relations to SPARQL, so queries can ask what is within, near or touching what.
Financial Industry Business Ontology 2014 standard
OWL ontology of financial contracts, instruments, parties and their relations, begun after the 2008 crisis as a shared vocabulary for analysis and regulatory reporting; developed by the EDM Council with the Object Management Group and in an open community process since 2020.
SHACL 1.2 2025 standard
Revision of SHACL by the W3C Data Shapes Working Group, in drafts since March 2025, adding modules for node expressions, rules, user interfaces, profiling and, from September 2026, inference rules that derive new triples from existing ones.

Projects 1

Protégé 1987 project
Free ontology editor from Stanford University, widely used to build OWL ontologies.

People and organizations (49)

Linked to works on this question; the number counts those works.

Doug Lenat (2) · Frank van Harmelen (2) · Ian Horrocks (2) · Jim Hendler (2) · Peter Patel-Schneider (2) · Ronald J. Brachman (2) · R.V. Guha (2) · World Wide Web Consortium (2) · Alberto García-Durán · Alex Krizhevsky · Alon Halevy · Antoine Bordes · Ashish Vaswani · Chen Chen · Clay Shirky · Cycorp · DARPA · Deborah McGuinness · Fernando Pereira · Geoffrey Hinton · Greg Corrado · Guus Schreiber · Hector Levesque · Ilya Sutskever · Jacob Devlin · James G. Schmolze · Jason Weston · Jeff Dean · Jiapu Wang · John McCarthy · Kai Chen · Kenton Lee · Kristina Toutanova · Linhao Luo · Marvin Minsky · Microelectronics and Computer Technology Corporation · Ming-Wei Chang · Nicolas Usunier · Oksana Yakhnenko · Pat Hayes · Peter Norvig · Shirui Pan · Tim Berners-Lee · Tomáš Mikolov · Waldo Tobler · William A. Woods · Xin Luna Dong · Xindong Wu · Yufei Wang