Research map / Large language models / Retrieval and knowledge
A Theory of Formalisms for Representing Knowledge
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a formal framework for knowledge representation formalisms (KRFs) based on query answering over databases and knowledge bases, and proves that all universal KRFs are recursively isomorphic (plus a result for equally strong KRFs with the padding property).
Problem
Resolving the longstanding dispute over which knowledge representation formalism is best (declarative vs. procedural; symbolic vs. connectionist; explicit vs. implicit knowledge) by a rigorous mathematical comparison of formalisms.
Approach
Defines knowledge bases abstractly as classes of database-query pairs closed under five natural properties, defines KRFs as recursive theory-to-KB mappings with recursively enumerable query checking, and constructs a canonical procedural universal KRF via a task-array simulation of Turing machines, showing all universal KRFs are recursively isomorphic.
Key results
- Proves that the canonical procedural KRF Θ is a universal and expressively complete KRF.
- Proves all universal KRFs over the same query setting are recursively isomorphic (Rogers-style argument).
- Proves all equally strong KRFs admitting the padding property are recursively isomorphic.
Surprising findings
- No declarative universal KRF can be linearly more succinct than the procedural canonical KRF Θ.
Limitations
- Results are purely theoretical and concern offline compilation; reasoning efficiency is not directly analyzed.
- Recursive isomorphism is an existence result and does not give practical translations.
- Whether natural logical languages give universal KRFs for general cases remains open.
Experimental setup
Builds on: Rogers isomorphism theorem Lindström's theorem circumscription abstract OMQA-ontology
Closest papers by meaning
- Towards a Formal Theory of Representational Compositionality (ICML 2025 · similarity 0.85)
- Position: The Platonic Representation Hypothesis (ICML 2024 · similarity 0.84)
- Emergent Symbolic Mechanisms Support Abstract Reasoning in Large Language Models (ICML 2025 · similarity 0.84)
- Deciphering Raw Data in Neuro-Symbolic Learning with Provable Guarantees (AAAI 2024 · similarity 0.83)
- Right for the Right Reasons: Avoiding Reasoning Shortcuts via Prototypical Neurosymbolic AI (NeurIPS 2025 · similarity 0.83)
- The Linear Representation Hypothesis and the Geometry of Large Language Models (ICML 2024 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.