When designing systems to understand natural language, map database queries, or learn action models for AI agents, computer scientists face a fundamental trade-off between expressivity (what a formal language can represent) and tractability (how easily a system can learn or search within that language).
To keep computation manageable, foundational frameworks across these domains frequently default to conjunctive logic—systems where rules, preconditions, or queries are formed strictly by chaining conditions together with an implicit "AND". While restricting representations to simple conjunctions or binary relations makes learning algorithms highly efficient and keeps search spaces small, it introduces a severe logical expressivity gap. Human language and real-world environments are inherently non-conjunctive; they are filled with alternatives ("OR"), exclusions ("NOT"), quantities ("every", "most"), and statistical summaries ("the maximum").
When a system's underlying formal grammar cannot express these concepts, it hits a hard structural ceiling. No matter how much data or optimization power is thrown at the model, it remains fundamentally incapable of capturing the nuance of the world it is trying to represent.
The Anatomy of the Conjunctive Bottleneck
The limitation of conjunctive logic manifests across several distinct areas of computer science, acting as a shared bottleneck for action planning, database querying, and explainable machine learning.
Action Planning and Rule Induction
In artificial intelligence planning, an agent must learn the "preconditions" required to execute an action safely. In Learning by Observation and Practice: A Framework for Automatic Acquisition of Planning Operators, Wang demonstrated that restricting operator learning to conjunctive preconditions circumvents the "knowledge engineering bottleneck" by making rule induction computationally efficient. However, the author noted that this leaves the framework entirely unable to represent disjunctive logic or conditional effects.
Decades later, this constraint still binds modern safe action modeling. Juba et al. show in Learning Safe Action Models with Partial Observability that while conjunctive constraints allow algorithms to guarantee plan execution safety under partial visibility, they lack the expressive power to handle complex, branching real-world rules.
The same bottleneck appears in explainable machine learning. When trying to make mixture models human-readable, Wilms et al. point out in Explainable Mixture Models through Differentiable Rule Learning that defining data sub-populations via pure conjunctive logic prevents the model from capturing alternative, disjunctive relationships among features.
Database Querying and Data Integration
A parallel limitation exists in data retrieval. When integrating diverse, heterogeneous web sources, systems must describe what kinds of queries a data source can answer. In Describing and Using Query Capabilities of Heterogeneous Sources, Vassalos argued that restricting capability descriptions to conjunctive logic completely excludes vital operations like negation, disjunction, and aggregation.
As a result, as Carman et al. later observed in Learning Semantic Descriptions of Web Information Sources, systems cannot accurately model or utilize information sources that provide statistical summaries or alternative data paths.
The Performance Ceiling in Semantic Parsing
The expressivity gap becomes most acute in semantic parsing—the task of translating natural language into executable code or structured queries (such as SPARQL or lambda-calculus).
If a user asks an analytical question, but the target grammar can only represent basic select-project-join operations, the system fails before the reasoning even begins. Marion et al. explicitly formalize this in Structured Context and High-Coverage Grammar for Conversational Question Answering over Knowledge Graphs: a low-expressivity grammar creates a strict performance ceiling. If a question cannot be mapped to a valid executable form within the grammar, a model's underlying reasoning capabilities become irrelevant.
Natural Language: "Which actors who are not American have won more than 2 Oscars?"
│
▼
[ Semantic Parser ]
│
▼
Target Grammar Limitations:
├─ No Negation (NOT) ❌
├─ No Aggregation (COUNT > 2) ❌
└─ Only Conjunctive Triples (Actor AND Won_Oscar) ⚠️
│
▼
Execution Failure: The system cannot construct a valid query graph.
This structural ceiling manifests across several dimensions of semantic parsing:
- Binary Relations vs. Rich Meanings: Krishnamurthy et al. show in Weakly Supervised Training of Semantic Parsers that frameworks restricted to extracting simple binary relations fail to capture the complex, multi-argument meanings embedded in natural language sentences.
- The Triple-Graph Constraint: In Knowledge Base Question Answering (KBQA), systems often map questions to basic triple-based query graphs. Zhang et al. demonstrate in Crake: Causal-Enhanced Table-Filler for Question Answering over Large Scale Knowledge Base that this rigid structure prevents the generation of sophisticated queries involving conditional filters or union operations.
- Analytical Operations: Yahya et al. demonstrate in Natural Language Questions for the Web of Data that interfaces restricted to basic conjunctive operations cannot answer analytical questions that require counting, finding extrema (e.g., "the highest"), or excluding specific criteria.
- Conversational Context: When moving from single questions to multi-turn dialogues, the required expressivity compounds. Iyyer et al. note in Search-based Neural Structured Learning for Sequential Question Answering that restricted grammars fail to handle sequential reasoning operations, such as computing set unions or simultaneously comparing multiple prior results.
Escaping the Bottleneck
To bridge the logical expressivity gap, researchers have shifted away from rigid, hand-crafted conjunctive formalisms toward flexible, high-coverage architectures that can handle richer target languages without sacrificing learnability.
Richer Target Formalisms
The realization that standard logical formalisms lack the expressive power to capture natural language meanings dates back to early computational linguistics. Epstein, in Principle-Based Interpretation of Natural Language Quantifiers, highlighted the necessity of developing more sophisticated target languages to handle the intricate relationships between quantifiers (like "every" or "many") and pronouns. Concurrently, Zajac proposed extending feature structure formalisms to support full logical expressions in A Transfer Model Using a Typed Feature Structure Rewriting System with Inheritance, demonstrating that inheritance-based rewriting could manage the complexity of mapping indirect speech acts between languages.
Generative and High-Coverage Grammars
Instead of forcing natural language into rigid, pre-defined logical templates, Ng et al. introduced a recursive generative process over "hybrid trees" in A Generative Model for Parsing Natural Language to Meaning Representations. This shifted the paradigm toward flexible formalisms capable of supporting complex structures like lambda-calculus.
By designing explicit, high-coverage logical grammars that natively accommodate counting, comparisons, and multi-hop reasoning, the authors of Structured Context and High-Coverage Grammar for Conversational Question Answering over Knowledge Graphs successfully shattered the performance ceiling that had constrained prior semantic parsers.
Policy Optimization for Complex Semantics
As the target formalisms grow more expressive, the space of possible logical forms expands exponentially, making traditional search methods intractable. Modern approaches solve this by pairing large language models with advanced reinforcement learning to navigate these complex spaces safely.
For example, in Enhancing AMR Parsing with Group Relative Policy Optimization, Barta et al. utilize Group Relative Policy Optimization (GRPO) with tailored reward signals to fine-tune models for Abstract Meaning Representation (AMR) parsing. This allows the system to accurately capture highly nuanced semantic structures and non-linear relationships within sentences, demonstrating a scalable path forward for high-expressivity semantic architectures.
Key Foundational Work
A Transfer Model Using a Typed Feature Structure Rewriting System with Inheritance (1989) — contributed 1 concept elements to this direction.
Principle-Based Interpretation of Natural Language Quantifiers (1988) — contributed 1 concept elements to this direction.