Skip to content
DraconiticResearch
Search Sources API
181,716 studies31 sourcesUpdated 15 min ago
PreprintCC BY-NC-ND 4.0arXiv

Contributions to the hierarchy of probabilistic languages

  • Lothar Sebastian Krapp
  • Remo Nitschke
Open at sourcePDFDOICite

Abstract

We reconsider the theory of probabilistic formal languages generated by n-gram models and by probabilistic context-free grammars (PCFGs). The expected hierarchy of probabilistic grammars is established by proving that every probabilistic language generated by an n-gram model is also generated by some PCFG, while some probabilistic languages generated by PCFGs cannot be generated by any n-gram model. We introduce the notion of fully connected PCFGs, namely PCFGs in Chomsky normal form where every production rule only involving non-terminals has non-zero probability. Our main result shows that any probabilistic language generated by an n-gram model differs from any probabilistic language generated by a fully connected PCFG. Therefore, the class of probabilistic languages generated by n-gram models is not a subset of the class generated by fully connected PCFGs.

Related

  1. Tree languages and branched groups
    Laurent Bartholdi, Marialaura Noce
    Mathematische ZeitschriftPeer-reviewedCC BYFull text2 citedAlgebra & number theoryHAL
  2. Recognizable Picture Languages: Separating UREC from coUREC via Communication Complexity
    Antonin Callard, Andrei Romashchenko, Véronique Terrier +1
    HALPreprintCC BY 4.0Full textGeneral mathematicsHAL
  3. Big Ramsey degrees and structures in relational languages
    Yifan Hu
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsLogic & foundationsarXiv
  4. Logical isomorphism and logical limit laws for small permutation classes and regular languages
    Klas Markström, Eero Räty
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  5. Internal Languages for Thin Epsilon-Hyperdoctrines: Soundness, Completeness, and Rocq Formalization
    Zoltán Gábor Molnár, Csaba Tóth
    arXivPreprintarXiv licenceFull textAlgebra & number theoryLogic & foundationsarXiv

Cite

BibTeXRIS
BibTeX
@misc{krapp2026contributions,
  title = {{Contributions to the hierarchy of probabilistic languages}},
  author = {Lothar Sebastian Krapp and Remo Nitschke},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.23567},
  eprint = {2609.23567},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.23567},
  note = {CC BY-NC-ND 4.0},
}
RIS
TY  - UNPB
TI  - Contributions to the hierarchy of probabilistic languages
AU  - Lothar Sebastian Krapp
AU  - Remo Nitschke
PY  - 2026
DA  - 2026/09/20
PB  - arXiv
DO  - 10.48550/arxiv.2609.23567
UR  - https://arxiv.org/abs/2609.23567
AB  - We reconsider the theory of probabilistic formal languages generated by n-gram models and by probabilistic context-free grammars (PCFGs). The expected hierarchy of probabilistic grammars is established by proving that every probabilistic language generated by an n-gram model is also generated by some PCFG, while some probabilistic languages generated by PCFGs cannot be generated by any n-gram model. We introduce the notion of fully connected PCFGs, namely PCFGs in Chomsky normal form where every production rule only involving non-terminals has non-zero probability. Our main result shows that any probabilistic language generated by an n-gram model differs from any probabilistic language generated by a fully connected PCFG. Therefore, the class of probabilistic languages generated by n-gram models is not a subset of the class generated by fully connected PCFGs.
ER  -