Skip to content

Formal Grammars & Parsing Complexity

← Back to Domain-Specific Families

Abstractions about formal grammars, parsing, and graph complexity measures, covering grammar classes constrained by production rules (leftist, noncontracting, and straight-line grammars), parsing algorithms and complexity classes (deterministic parsing, LOGCFL), and structural graph parameters like aperiodicity and twin-width.

7 abstractions in this family — domain-specific abstractions that sit near one another in structural-signature space (k-means over structural-signature embeddings). Each is shown with its short description.

  • Aperiodic graph — In the mathematical area of graph theory, a directed graph is said to be aperiodic if there is no integer k > 1 that divides the length of every cycle of the graph.
  • Deterministic parsing — In natural language processing, deterministic parsing refers to parsing algorithms that do not backtrack.
  • Leftist grammar — In formal language theory, a leftist grammar is a formal grammar on which certain restrictions are made on the left and right sides of the grammar's productions.
  • LOGCFL — In computational complexity theory, LOGCFL is the complexity class that contains all decision problems that can be reduced in logarithmic space to a context-free language.
  • Noncontracting Grammar — In formal language theory, a noncontracting grammar (also called monotonic grammar) is a type of formal grammar whose production rules never decrease the total length of a string during derivation.
  • Straight-Line Grammar — A straight-line grammar (SLG) is a formal grammar that generates exactly one string.
  • Twin-width — A graph parameter equal to the least possible maximum red degree over all complete vertex-contraction sequences that mark adjacency disagreements.