# The Generation-Recognition Asymmetry: Six Dimensions of a Fundamental Divide in Formal Language Theory

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 95 references that are in the map.
- First posted on arXiv 10 Mar 2026.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [New Bounds for Matrix Multiplication: from Alpha to Omega](https://mlsanity.com/paper/2307.07970/) (2023)
- [Designing RNA Secondary Structures is Hard](https://mlsanity.com/paper/1710.11513/) (2017)
- [Dual Supervised Learning for Natural Language Understanding and Generation](https://mlsanity.com/paper/1905.06196/) (2019)
- [Towards Unsupervised Language Understanding and Generation by Joint Dual Learning](https://mlsanity.com/paper/2004.14710/) (2020)
- [AMR-to-text generation as a Traveling Salesman Problem](https://mlsanity.com/paper/1609.07451/) (2016)
- [Generative Statistical Models with Self-Emergent Grammar of Chord Sequences](https://mlsanity.com/paper/1708.02255/) (2017)

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

- [MultiFixer: A Coordinator-Proposer Based Multi-Agent Framework For Fixing Multi-Hunk Bugs](https://mlsanity.com/paper/2607.26591/) (2026)

## Abstract (arXiv)

Every formal grammar defines a language and can in principle be used in three ways: to generate strings (production), to recognize them (parsing), or -- given only examples -- to infer the grammar itself (grammar induction). Generation and recognition are extensionally equivalent -- they characterize the same set -- but operationally asymmetric in multiple independent ways. Inference is a qualitatively harder problem: it does not have access to a known grammar. Despite the centrality of this triad to compiler design, natural language processing, and formal language theory, no survey has treated it as a unified, multidimensional phenomenon. We identify six dimensions along which generation and recognition diverge: computational complexity, ambiguity, directionality, information availability, grammar inference, and temporality. We show that the common characterization "generation is easy, parsing is hard" is misleading: unconstrained generation is trivial, but generation under constraints can be NP-hard. The real asymmetry is that parsing is always constrained (the input is given) while generation need not be. Two of these dimensions -- directionality and temporality -- have not previously been identified as dimensions of the generation-recognition asymmetry. We connect the temporal dimension to the surprisal framework of Hale (2001) and Levy (2008), arguing that surprisal formalizes the temporal asymmetry between a generator (surprisal = 0) and a parser that predicts under uncertainty (surprisal > 0). We review bidirectional systems in NLP and observe that bidirectionality has been available for fifty years yet has not transferred to most domain-specific applications. We conclude with a discussion of large language models, which architecturally unify generation and recognition while operationally preserving the asymmetry.