Contributions to the hierarchy of probabilistic languages
Lothar Sebastian Krapp, Remo Nitschke
cs.FL · cs.CL · math.LO · math.PR
Quick verdict
Establishes strict n-gram/PCFG hierarchy and fully connected PCFGs; disjointness idea convincing but Theorem 4.4 proof chain has a gap
Summary
The paper studies probabilistic languages - probability distributions with strictly positive mass on every non-empty string - generated by n-gram models and by probabilistic context-free grammars (PCFGs) in Chomsky normal form. It first re-establishes, in this quantitative setting, a strict hierarchy: unigram below bigram below trigram below PCFG. Construction 3.1 embeds any n-gram model into an (n+1)-gram model, Example 3.2 (with Remark 3.3 and Example 3.4) proves strictness, and Constructions 3.5/3.6 embed any n-gram language into a CNF PCFG. The main contribution introduces fully connected PCFGs (Definition 2.6), where every binary nonterminal rule X-YZ has positive probability, and proves (Theorem 4.4) that no n-gram language coincides with any fully connected PCFG language. The argument compares growth rates: n-gram models give P(a^l) a purely geometric decay (Lemma 4.1), while full connectivity forces a polynomial-times-geometric lower bound (Lemma 4.3), because Catalan-many parse trees contribute to a^l (Example 3.7). Caveat: a central inequality chain in the proof implicitly requires every nonterminal to derive every a^j, which full connectivity alone does not guarantee - the result is likely true, but the argument needs repair. Other limitations: purely qualitative growth-rate statements, idealized all-strings-positive assumptions, and a heuristic likelihood claim (Remark 4.5).
Review complete
Assessment at a glance
4
risk flags identified
● high 1
● medium 2
● low 1
4 strengths · 5 weaknesses · 5 author questions
AI text signal = Binoculars zero-shot detector score over 20 sampled passages (Fast-DetectGPT co-reported) — absence does not prove human authorship, and a flag does not imply misconduct.
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- In the strictly positive setting of Definition 2.1, probabilistic languages form a strict chain unigram < bigram < trigram < ... < n-gram < ... < PCFG.
- Every probabilistic language generated by an n-gram model can also be generated by some PCFG in Chomsky normal form (Constructions 3.5 and 3.6).
- Fully connected PCFGs (Definition 2.6) always generate probabilistic languages in the sense of Definition 2.1, unlike merely consistent CNF PCFGs (Example 2.8).
- Theorem 4.4: for any n-gram model G and any fully connected PCFG H, the generated distributions satisfy P_G != P_H; combined with Constructions 3.5/3.6 this makes the n-gram class a proper subset of, and disjoint from, the fully connected PCFG class.
- Remark 4.5: the growth-rate separation implies the true generating model attains higher likelihood than any fully connected PCFG on a sufficiently long corpus.
Strengths
Clean quantitative reformulation of the Chomsky hierarchy
Definition 2.1 fixes the object of study (distributions with strictly positive mass on all of Sigma+), and the chain unigram < bigram < ... < PCFG (Section 3, display 3.1) is recovered quantitatively via explicit padding (Construction 3.1) and minimal counterexamples (Examples 3.2, 3.4).
Verifiable, minimal separating witnesses
Example 3.2 reduces equality of two distributions to a single contradictory transition ratio (1/(9k(k+1)) vs 1/(3(k+1))); Example 3.4 does the same for unigram vs bigram via P(aab)=P(aba), forcing 1/(3k)=2/3. Both are a few lines and easy to check.
The growth-rate idea behind the main theorem is transparent and inspectable
Genuine relevance beyond mathematics
Weaknesses
Main proof gap in Theorem 4.4
Class-level framing outruns the element-level theorem
Purely qualitative growth-rate statements
Idealized positivity assumption
Proofreading and equation hygiene
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
Report preview
Preliminary Review: Contributions to the hierarchy of probabilistic languages (arXiv:2609.23567)
The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.
- All 4 strengths & 5 weaknesses, analyzed in detail
- 4 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 5 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
Frequently asked questions
Do n-gram models and probabilistic context-free grammars generate the same probabilistic languages?
Not exactly. According to this paper, every probabilistic language generated by an n-gram model can also be generated by some PCFG in Chomsky normal form, but no n-gram model's language coincides with the language of any fully connected PCFG (one where every binary nonterminal rule has positive probability). So n-gram languages form a strict subclass that is disjoint from the fully connected PCFG class.
How does the paper show n-gram models and fully connected PCFGs differ?
By comparing how fast probabilities of a^l (the string of l copies of 'a') decay. For any n-gram model the probability decays purely geometrically, like a constant times r^l. A fully connected PCFG has Catalan-number-many parse trees for a^l, each with a positive probability product, forcing a polynomial-times-geometric lower bound. Two distributions with different growth laws on the same strings cannot be equal. Caveat: the printed proof contains a step a reviewer would contest, though the result is likely repairable.
Has this paper been peer reviewed?
No. It is version 1 of arXiv preprint 2609.23567, submitted 20 September 2026 by L. S. Krapp and R. Nitschke (University of Zurich / University of Konstanz), funded by the Swiss NCCR Evolving Language. This is an independent preliminary review, not a journal or conference decision.
Why do fully connected PCFGs matter for likelihood calculations?
The paper requires every grammar to assign positive probability to every possible non-empty string. Full connectivity guarantees this for PCFGs in Chomsky normal form, so the likelihood of any observed corpus (a product of string probabilities) is strictly positive and well-defined for every grammar in the comparison - letting the class-level separation translate into likelihood-based model discrimination.
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
- Text was extracted from the PDF; a few displayed equations appear to have dropped factors or trailing terms (e.g. Lemma 4.1's equality chain, Example 3.2's final inequality), so typographic judgments on formulas are tentative.
- Figure 1 is only available via its caption; the plotted log-probability decay curves could not be inspected.
- The identified proof gap is based on the printed text; the authors may hold a corrected argument not visible here.
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.