# Greedy Grammar Induction with Indirect Negative Evidence

arXiv: https://arxiv.org/abs/2312.15321 · HTML: https://mlsanity.com/paper/2312.15321/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 2 of its 50 references that are in the map.
- First posted on arXiv 23 Dec 2023.

## Builds on (most cited first, 2 of 2)

- [Compound Probabilistic Context-Free Grammars for Grammar Induction](https://mlsanity.com/paper/1906.10225/) (2019)
- [PCFGs Can Do Better: Inducing Probabilistic Context-Free Grammars with Many Symbols](https://mlsanity.com/paper/2104.13727/) (2021)

## Built on by (most cited first, 1 of 1)

- [Agentic AI platforms for autonomous training and rule induction of human-human and virus-human protein-protein interactions](https://mlsanity.com/paper/2604.23924/) (2026)

## Abstract (arXiv)

This paper proposes a non-lexicalized grammar-induction procedure that separates two tests: recognition of the observed finite presentation, and rejection of short preterminal strings generated by a hypothesis but unsupported by the evidence. The central object is the rule-coverage bound (ℓ^*(G)): the maximum, over rules in (G), of the length of the shortest preterminal string whose derivation uses that rule. This bound induces the comparison universe (Sigmapre≤ ℓ^*(G)), where unsupported generated strings serve as indirect evidence against overgenerating hypotheses. We give a greedy search algorithm over rule sets and prove a conditional weak-recovery theorem: under explicit reachability conditions and sufficient saturation of the presentation, the exact learner reaches a grammar weakly equivalent to the unknown target. The complexity analysis is slice-wise: for each fixed incrementality radius (k), the search explores polynomially many rule-set extensions in the finite rule universe. Across 31 benchmark runs spanning Dyck-(k) languages ((1≤ k≤4)), palindromes, (an bn), English-like recursive fragments, and an inherently ambiguous union language, grammar-level analysis establishes weak equivalence between every returned grammar and its target.