Research

The Generation-Recognition Asymmetry

Six Dimensions of a Fundamental Divide in Formal Language Theory, Romain Peyrichou. arXiv preprint 2603.10139, 10 March 2026; submitted to Information and Computation. 32 pages, 6 figures, 4 tables. Read the PDF.

A formal grammar serves three purposes: generating strings, recognizing them, or inferring the grammar from examples. Generation and recognition define the same language, but they do not cost the same. The paper separates six dimensions of this gap: computational complexity, ambiguity, directionality, information availability, grammar inference, and temporality.

The thesis: the common phrase “generation is easy, parsing is hard” is misleading. Unconstrained generation is trivial; generation under constraints can be NP-hard. The real asymmetry is that parsing is always constrained, since the input is given, while generation need not be.

Two of the six dimensions, directionality and temporality, had not been identified before as dimensions of this asymmetry. The temporal dimension connects to surprisal as defined by Hale (2001) and Levy (2008): zero for the generator, positive for a parser that predicts under uncertainty. The paper ends with large language models, which unify generation and recognition in one architecture while preserving the asymmetry in how they operate.

The series of articles on this site that accompanies the preprint:

• L13 — Generate or Recognize
• L14 — Parsing direction
• L15 — The Formulas of Asymmetry
• L16 — The Paradox of Bidirectionality
• L17 — The Complexity Matrix
• L18 — Sign Reversal
• L19 — The P-chain
• L20 — Inference

The Two-Vīṇā Experiment

Bharata’s Nāṭyaśāstra (chapter XXVIII, śloka 24) describes an experiment: two vīṇās tuned the same way, one of which is lowered step by step to establish the size of the intervals. The application lets you redo it in the browser. One vīṇā stays fixed; on the other, you move the pegs yourself, play the notes and hear the beats between the two instruments, which vanish when two notes merge. A first stage tunes the Sa-grāma by ear; the second follows the four successive lowerings, which establish that the pramāṇa śruti exists and that the intervals of two śrutis, of a tone and of a minor third are identical to one another.

The demonstration and its analysis come from Bernard Bel (The two-vina experiment): the experiment yields 7 equations and 3 inequalities between the 22 śruti sizes, so the pramāṇa śruti remains free between about 0 and 56.8 cents. The application adds interpretive choices that it flags itself: notes at Pythagorean ratios, a pramāṇa śruti set to 81/80 (about 21.5 cents), one convention among others, and a first tuning stage that is a teaching reconstruction: the treatise assumes the vīṇā is already tuned. The interface is in French. Source: Nāṭyaśāstra XXVIII.24, after Bernard Bel’s reconstruction (A Mathematical Discussion of the Ancient Theory of Scales according to Natyashastra, CNRS, 1988; bolprocessor.org/two-vina-experiment). Bel notes that no English translation of these chapters is available; he relies on their restatement by Śārṅgadeva in the Saṅgītaratnākara (trans. R. K. Shringy, vol. I, Motilal Banarsidass, 1978).