Boundedness Constraints for Tractable Grammar Parsing

31 concepts23 papers1 proposal

To capture the rich, layered syntax of natural language, computer scientists and linguists have developed highly expressive grammar formalisms. Frameworks like unification grammars, Combinatory Categorial Grammars (CCGs), and Macro grammars easily model complex linguistic phenomena such as long-distance dependencies and agreement features.

However, this expressive power comes at a steep computational cost. Unconstrained, many of these advanced formalisms are Turing-complete, meaning that determining whether a sentence is grammatically valid is undecidable. Even when decidable, the search space can explode exponentially.

To bridge the gap between linguistic expressiveness and computational tractability, researchers rely on boundedness constraints. The core intuition is simple: allow the grammar to remain highly expressive, but strictly limit the dimensions along which it can generate infinite loops or unbounded memory states. By clipping these infinite paths, complex languages can be mapped into finite or polynomial-time verifiable spaces.

Halting Infinite Loops via Derivation Boundedness

The most direct threat to a parser's ability to halt is infinite recursion. This occurs when a grammar can apply production rules indefinitely without actually consuming any words from the input string (such as through empty productions or cyclic unary rules).

To solve this for unification grammars, Andrew R. Haas in Parallel Parsing for Unification Grammars introduces a constraint that limits the number of derivations allowed for short strings (specifically strings of length zero or one). Why does this work? By ensuring that a single word or empty space cannot trigger an infinite chain of rule applications, the parser is guaranteed to halt, transforming an undecidable grammar into a solvable one.

A similar principle applies to more complex grammar types. In Inside-Outside Algorithm for Macro Grammars, Ryuta Kambe et al. apply an "expansive restriction" to grammar rules. This structural constraint ensures that all possible derivation sequences remain finite, preventing infinite recursion when building type-based derivation trees.

Even in grammar induction—where a system tries to learn a grammar from data—unboundedness poses a threat known as the limit point problem, where a learner can get lost in infinite ascending chains of increasingly complex grammars. As demonstrated by Hendrik Blockeel in Identification of Hyperedge-Replacement Graph Grammars, restricting the number of times a terminal label can appear in a production rule eliminates these infinite chains, making it theoretically possible for a learning algorithm to converge on the correct grammar.

In practical engineering scenarios, such as natural language generation, these theoretical bounds are often mirrored by heuristic "circuit breakers." As Claire Gardent explains in Generation for Grammar Engineering, production rules can easily spin into infinite generation loops. Implementing hard caps—such as maximum tree depths or timeouts—safeguards the system, though it risks hiding deep rule interactions.

Capping Memory: Structural and Valency Bounds

When a sentence contains long-distance dependencies (for example, a word that has moved far from its original syntactic position), a parser must keep track of this "displaced" element in memory until its role is resolved. If a grammar allows an arbitrary number of these dependencies to remain open simultaneously, the parser's state space explodes.

Linguistically, human languages naturally avoid this explosion through locality constraints. Robert C. Berwick et al. in Syntactic Constraints and Efficient Parsability argue that deterministic, single-pass parsers require these strict boundaries on dependency distances to prevent their search windows and memory requirements from expanding indefinitely.

To formalize this mathematically, Alexander Ja. Dikovsky in Grammars for Local and Long Dependencies introduces a constant bound on the number of "unsaturated valencies" (unresolved syntactic slots) allowed at any single point during a derivation. By capping the number of simultaneous open dependencies, the grammar is prevented from entering complex, non-context-free states, preserving a highly efficient $O(n^3)$ cubic-time parsing complexity.

Similarly, Meaghan Fowlie et al. show in Parsing Minimalist Languages with Interpreted Regular Tree Grammars that limiting the number of active displaced elements in storage is the key to keeping the parsing of Minimalist Grammars computationally tractable.

On a broader structural level, Georg Zetzsche leverages "breadth-boundedness" in An approach to computing downward closures. By enforcing a strict limit on the number of active non-terminals during a word's derivation, highly complex language representations can be safely mapped to simpler formalisms where language membership tests become fully decidable.

Collapsing the State Space: Feature and Parameter Finiteness

Many modern grammars use variables and features (like gender, number, or tense) to ensure grammatical agreement. If these features can take an infinite variety of values or form deeply nested structures, the grammar quickly becomes equivalent to a Turing machine.

To prevent this, researchers enforce finite domains on variables. Sylvain Schmitz et al. demonstrate this in Feature Unification in TAG Derivation Trees. By restricting features to finite domains, feature-based Tree Adjoining Grammars (TAGs) are kept computationally equivalent to regular tree grammars, avoiding undecidability.

This strategy is echoed in document authoring systems. Marc Dymetman in Document Content Authoring and Hybrid Knowledge Bases utilizes finite parameterization, forcing variables to draw only from a predefined set of constants. This design choice guarantees that checking the validity of logical constraints remains completely decidable.

The underlying theoretical principle here is often "size-preservation." As formalized by David J. Weir in Linear Context-Free Rewriting Systems and Deterministic Tree-Walking Transducers, computational tractability is guaranteed when combining two grammatical structures only introduces a bounded amount of new information. This keeps the language within a mildly context-sensitive boundary, enabling polynomial-time processing.

Following this logic, Nobo Komagata in Generative Power of CCGs with Generalized Type-Raised Categories applies strict structural constraints to the direction of slashes and the size of arguments passed between categories, ensuring that variable-heavy CCGs do not drift into intractability.

Managing the Tensions of Boundedness

Enforcing hard bounds creates a natural tension: what happens if a legitimate linguistic structure requires an unbounded representation? For example, adding an arbitrary number of modifiers (adjunct addition) can theoretically cause a parser to loop.

To resolve this without causing infinite loops, Mark Johnson 0001 et al. in Memoization of Coroutined Constraints propose a coroutining framework. Instead of evaluating potentially infinite rules immediately, the parser delays their evaluation until the relevant grammatical categories are sufficiently instantiated, preventing exponential search spaces.

In other cases, normal-form constraints designed to optimize parsing can conflict with practical bounds. Yonatan Bisk et al. note in Normal-form parsing for Combinatory Categorial Grammars with generalized composition and type-raising that certain edge cases require an unbounded degree of type-raising to find a valid parse, creating a direct conflict with the strict bounds used in practical implementations.

When an infinite category space is unavoidable, researchers turn to finite approximations. In From OpenCCG to AI Planning: Detecting Infeasible Edges in Sentence Generation, Maximilian Schwenger et al. use a size-bound parameter to map an infinite grammar into a finite planning space.

The authors configure these approximations in two ways:

  • Optimistic approximations: Over-approximate possibilities to ensure that no valid sentence is accidentally pruned.
  • Pessimistic approximations: Under-approximate possibilities to aggressively reduce the search space, accepting the risk of missing some valid solutions.

By dynamically tuning these bounds, modern parsers can navigate the boundary between infinite linguistic expression and finite computational reality.

Key Foundational Work

Parallel Parsing for Unification Grammars (1987) — contributed 4 concept elements to this direction.
Parallel Parsing for Unification Grammars (1987) — contributed 3 concept elements to this direction.
Syntactic Constraints and Efficient Parsability (1983) — contributed 1 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_grammar_boundedness_constraint_b109e712,
  title = {grammar boundedness constraint},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/grammar-boundedness-constraint/rdr_b109e7126d7d40ffb911ce0e5db14c91},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_grammar_boundedness_constraint_b109e712_v1,
  title = {grammar boundedness constraint},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/grammar-boundedness-constraint/rdr_b109e7126d7d40ffb911ce0e5db14c91/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake