Modeling Linguistic Derivation as Resource Consumption

31 concepts16 papers1 proposal

When we reason using classical logic, facts are treated as truth values that can be reused indefinitely. If you know that a proposition $A$ is true, you can use it to derive $B$, and you still retain the knowledge that $A$ is true. In mathematical terms, classical logic permits the structural rules of weakening (allowing you to discard unused assumptions) and contraction (allowing you to duplicate assumptions).

Natural language, however, does not work this way. If you have the words "the", "cat", and "sat", you cannot arbitrarily duplicate "cat" to produce "the cat cat sat", nor can you discard "sat" and still have a well-formed sentence. In language, words, syntactic features, and semantic meanings act as finite, consumable tokens.

To capture this behavior, computational linguists treat grammatical deduction and semantic assembly not as classical truth verification, but as resource management. By utilizing linear logic—a framework where premises are treated as resources that must be consumed exactly once—we can model the precise ways language constructs meaning without losing or duplicating information.

The Core Engine: Linear Logic

As noted by Koen Versmissen in Categorial grammar, modalities and algebraic semantics, any logical system designed to model natural language grammar must be resource-preserving. By eliminating weakening and contraction, we force the grammar to account for every single occurrence of a linguistic type.

This strict accounting is perfectly realized in the multiplicative fragment of linear logic. Philippe de Groote leverages this fragment in Towards Abstract Categorial Grammars to create a unified, reversible architecture where both syntax and semantics are mapped from a shared abstract structure. Because the underlying logic is linear, it inherently prevents the accidental deletion or duplication of information during translation between surface forms and meanings.

Classical Logic:  A ⊢ A ⊗ A  (Information can be duplicated)
Linear Logic:     A ⊢ A      (Information is a finite resource)

This resource-sensitive perspective allows us to view parsing as a form of linear deduction. Glyn Morrill demonstrates in Higher-order Linear Logic Programming of Categorial Deduction that compiling categorial grammar rules into dynamic linear clauses provides an elegant, systematic way to parse language while guaranteeing that every lexical item is utilized exactly once.

The strategy is so robust that it can even unify competing linguistic paradigms. For example, Alain Lecomte et al. show in Extending Lambek Grammars: a Logical Account of Minimalist Grammars that the feature-checking operations in Chomsky’s Minimalist Program can be entirely reframed as linear resource consumption: a syntactic structure is valid if and only if all its required feature "tokens" are cleanly consumed by matching operations.

Glue Semantics and the Problem of Sharing

If linear logic dictates that every resource must be consumed exactly once, how do we handle linguistic phenomena where a single word or concept seems to influence multiple parts of a sentence? Consider coordination, as in "John saw and praised Mary", where "Mary" serves as the object for both verbs.

In Lexical-Functional Grammar (LFG), this is resolved via "Glue Semantics." As shown by Mary Dalrymple et al. in LFG Semantics via Constraints, linear logic can be used as an order-independent "glue" to assemble meaning fragments directly from unordered functional structures (f-structures).

To handle the apparent paradox of a single meaning being shared across multiple dependencies without violating linearity, Andrew Kehler et al. propose a shift in perspective in The Semantics of Resource Sharing in Lexical-Functional Grammar. Instead of treating the semantic meaning itself as the consumable resource, the logic treats the grammatical paths within the f-structure as the resources.

When an element is shared, it becomes accessible via multiple distinct pathways. The linear logic engine consumes these path-resources precisely once, ensuring that the structural integrity of the sentence is tightly controlled while still allowing a single semantic entity to contribute to multiple predicates. This framework proves highly practical for real-world applications; François Lareau et al. demonstrate in Collocations in Multilingual Natural Language Generation: Lexical Functions meet Lexical Functional Grammar that resource-based semantic mapping provides a reliable way to bind abstract meanings to language-specific syntactic structures during text generation.

Managing Contextual Licensing

Resource-sensitive logic also provides an elegant mechanism for handling contextual constraints and optional dependencies. A classic example is the distribution of Negative Polarity Items (NPIs) like "any" or "ever", which are only grammatical in certain contexts, such as under the scope of negation ("I don't have any" vs. *"I have any").

In Negative Polarity Licensing at the Syntax-Semantics Interface, John Fry models this interaction by treating semantic licensing requirements as logical resources. A negative word acts as a provider that generates a licensing resource, which the NPI subsequently consumes.

To handle sentences where an NPI is optional or absent, the system introduces a reclamation mechanism: if the licensing resource is not consumed by a dependent item, the provider reclaims its own resource. This ensures that the overall logical proof remains perfectly balanced, preventing leftover premises from invalidating an otherwise well-formed sentence.

With NPI:     [Negation] ──(Provides License)──> [NPI] (Consumes) ──> Balanced Proof
Without NPI:  [Negation] ──(Provides License)──> [Reclaimed]      ──> Balanced Proof

A similar "needs/provides" validation logic is used by Lionel Clément et al. in Generating Parallel Multilingual LFG-TAG Grammars from a MetaGrammar to automatically verify grammar rules. If a generated rule requires a subject or object resource that cannot be satisfied by the available components, the rule is discarded as structurally invalid.

This foundational concept of linearity is so powerful that it extends beyond linguistics into state-based planning. As demonstrated in Creativity and Artificial Intelligence, enforcing a linearity restriction on logical connections ensures that actions in a physical environment consume and produce states realistically, preventing the accidental duplication of real-world resources.

Algorithmic Realities and Complexity

While treating language as a resource-sensitive proof structure is theoretically elegant, it introduces severe computational challenges. In a standard chart parser, intermediate phrases can be freely reused. In a resource-sensitive parser, however, the system must meticulously track which specific tokens have been consumed to prevent a single word from being used multiple times in different branches of a parse tree.

This tracking requirement drastically increases the search space. Jochen Dörre proves in Parsing for Semidirectional Lambek Grammar is NP-Complete that when a grammar allows the flexibility needed to handle complex linguistic "gaps" (such as non-peripheral extraction), managing the fixed set of resources makes the parsing problem NP-complete.

To mitigate this complexity, researchers rely on specialized indexing and tracking mechanisms:

  • Index Merging: Mark Hepple in A Compilation-Chart Method for Linear Categorial Deduction introduces a compilation method that assigns unique index sets to initial resources. When formulas are combined during chart parsing, their index sets are merged, allowing the parser to instantly reject any derivation that attempts to reuse an already-consumed resource.
  • Polarity and Valency Tracking: Interaction Grammars, introduced by Guy Perrier in Interaction Grammars, use polarized features—analogous to chemical valencies—to drive syntactic composition via linear logic. To parse these structures efficiently without falling back on generic constraint solvers, Joseph Le Roux in Deductive Parsing in Interaction Grammars designs an Earley-style deductive parsing framework. The parsing state explicitly tracks the lifecycle of each node—categorizing them as available from the lexicon, obligatory for the current sub-parse, or already incorporated.

Despite the computational hurdles, this framework has successfully scaled to real-world language data. Konstantinos Kogkalidis et al. demonstrated this feasibility by creating ÆTHEL: Automatically Extracted Typelogical Derivations for Dutch, a large-scale corpus of over 72,000 sentences mapped to fully validated, resource-sensitive linear logic derivations.

Interestingly, the exact same tension between safety and resource tracking appears in computer science. As explored by Arnaud Spiwack et al. in Linearly qualified types: generic inference for capabilities and uniqueness, linear type systems in programming languages are highly effective for managing system capabilities and memory safety without leaks. Just as in parsing, explicitly threading these tokens manually is cumbersome; by treating them as implicit constraints, modern type systems can enforce strict, use-once resource management behind the scenes.

Key Foundational Work

Categorial grammar, modalities and algebraic semantics (1993) — contributed 4 concept elements to this direction.
The Semantics of Resource Sharing in Lexical-Functional Grammar (1995) — contributed 4 concept elements to this direction.
Higher-order Linear Logic Programming of Categorial Deduction (1995) — contributed 2 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_resource_sensitive_linguistic_modeling_aa0a75e5,
  title = {resource-sensitive linguistic modeling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/resource-sensitive-linguistic-modeling/rdr_aa0a75e513564c2bbead8dff1d193a6f},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_resource_sensitive_linguistic_modeling_aa0a75e5_v1,
  title = {resource-sensitive linguistic modeling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/resource-sensitive-linguistic-modeling/rdr_aa0a75e513564c2bbead8dff1d193a6f/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake