L16) The Paradox of Bidirectionality

Series: “Generation-Recognition Asymmetry”

This article accompanies the research paper The Generation-Recognition Asymmetry: Six Dimensions of a Fundamental Divide in Formal Language Theory (📄 arXiv).
Reading thread: L13 · L14 · L15 · L16 · L17 · L18 · L19 · L20 — or the complete index.

50 Years of Forgotten Reversible Grammars

Since the 1970s, grammatical formalisms capable of operating in both directions—generation and analysis—have existed in natural language processing. Yet, most formal systems in other fields remain stubbornly unidirectional. This paradox reveals that the asymmetry between generation and recognition is not a simple technical problem: it is a structural divide that even five decades of solutions have not bridged.

Where Does This Article Fit In?

In L13, we saw that certain systems—GF, unification grammars, the Bol Processor—are designed to work in both directions. In L14, we explored the directional dimension of asymmetry. In L15, we laid the mathematical foundations.

This article asks the question that follows from all this: if bidirectionality has been possible and available for 50 years, why isn’t it everywhere?

Why Does It Matter?

Imagine if a machine translator could only translate from French to English, never the reverse. And you were told: “the technology to do the reverse has existed since 1972, but no one uses it.”

This is exactly the situation for formal grammars in most applied fields. In bioinformatics, grammars predict RNA structure (analysis) but do not design sequences (generation). In musicology, grammars compose (generation) or analyze, but almost never both with the same formalism. In compilation, parsing and code generation are two separate modules.

Understanding why this situation persists means understanding the deep nature of asymmetry—and identifying the levers to overcome it.

The Idea in One Sentence

Bidirectional formalisms have existed in NLP since the 1970s but have not been transferred to other fields because bidirectionality requires declarativity—and most applied grammars are procedural.

Explaining Step by Step

1. The Landscape Map: Who Does What?

Let’s start by taking inventory. We can classify formal systems according to the directions they support:

System	Domain	Gen	Parse	Inference	Bidirectional
LL/LR Parsers	Compilers	—	✓	—	—
Earley/CYK	Formal languages	—	✓	—	—
NLG Pipeline	NLP	✓	—	—	—
NLG Templates	NLP	✓	—	—	—
LLMs (GPT, etc.)	NLP	✓	(implicit)	—	—
DCG (Prolog)	NLP	✓	✓	—	✓*
FST (morphology)	Linguistics	✓	✓	—	✓
GF (Ranta)	Multilingual NLP	✓	✓	—	✓
KAMP (Appelt)	NLP	✓	✓	—	✓*
Strzalkowski	NLP	✓	✓	—	✓
L* (Angluin)	Formal languages	—	—	✓	—
Gold	Formal languages	—	—	✓	—
BP3	Music	✓	✓	—	✓

\ Bidirectional in principle but with asymmetrical pathologies (DCG) or impractical cost (KAMP).*

Three observations stand out:

Most systems are unidirectional. They perform either generation or parsing, rarely both.
Bidirectional systems are concentrated in NLP (natural language processing), where the practical need for both directions (translation, dialogue, grammar engineering) stimulated development.
Grammatical inference (the “third direction”) is almost always separated from the other two.

2. The Pioneers of Bidirectionality

DCG: Bidirectionality through Prolog (1972)

Definite Clause Grammars (DCG), integrated into Prolog, are inherently bidirectional: the same grammar can be queried in both directions thanks to unification and backtracking.

But the symmetry is algorithmic, not computational. Left-recursive rules cause infinite loops in top-down parsing—but not in generation. Conversely, right-recursive rules can cause generation to diverge. The same grammar, in two directions, encounters different pathologies. This is a concrete illustration of directional asymmetry (L14).

FST: Mathematical Inversion (1983)

Finite-state transducers (FST), used in computational morphology, have an elegant property: the inverse of an FST is also an FST. If $$T$$ transforms underlying forms into surface forms (generation), then $T^{-1}$ does the reverse (analysis).

Koskenniemi’s two-level morphology (1983) exploits this directly. But this inversion property holds only for finite-state machines—it does not generalize to context-free grammars, where inversion is generally undecidable.

Q-systems: Reversible Computation (1970)

Colmerauer’s Q-systems (1970), precursors to Prolog, were designed from the outset for reversible computation. Their influence persists in logic programming, where the separation between logic and control (Kowalski, 1979) makes direction a parameter rather than an architectural choice.

3. Grammatical Framework: Large-Scale Bidirectionality

GF (Grammatical Framework, Ranta, 2004) is the most accomplished modern bidirectional system. Its architecture separates two levels:

Abstract syntax: the representation of meaning, independent of language
Concrete syntax: the surface realization, specific to each language

The same abstract tree can be linearized (generation: tree → sentence) or parsed (recognition: sentence → tree) in any of the 40+ supported languages.

GF demonstrates that bidirectionality is achievable at scale. But it requires an architectural commitment: the grammar must be written declaratively, with meaning and form properly separated.

4. The Cost of Bidirectionality

KAMP: Computationally Impracticable

Appelt (1985, 1987) attempted a unified architecture for planning and realization in text generation. He formulated what is perhaps the most important observation:

“The most fundamental requirement of any bidirectional grammar is that it be represented declaratively. If it is procedural, asymmetry is inevitable.”

His KAMP system worked—but was “computationally impracticable.” The cost of unifying planning and realization within a single framework proved prohibitive.

This is a cautionary result: bidirectionality is possible in principle but costly in practice.

Grammar Inversion: Strzalkowski

Rather than designing a bidirectional grammar from the start, Strzalkowski (1993) developed techniques to automatically transform a parsing grammar into a generation grammar—by inverting the control structure while preserving the declarative content.

The results: inversion works, but the inverted grammar is less efficient, and some constructions resist inversion entirely. The very fact that an inversion process is necessary proves the operational asymmetry.

Goodman and Bond’s Bidirectional Test

Goodman and Bond (2009) provided the most convincing empirical evidence of the value of bidirectionality: testing an HPSG grammar in both parsing and generation revealed errors invisible in unidirectional use, increasing coverage by 18%.

Moral: using a grammar in only one direction means testing only half of its properties.

5. Why Bidirectionality Has Not Been Transferred

If bidirectionality has existed for 50 years in NLP, why isn’t it everywhere?

Hypothesis 1: The requirement of declarativity. Appelt said it: bidirectionality requires declarative grammars—which say what without saying how. Yet most applied grammars are procedural: they embed the processing direction within the grammar itself. A shape grammar in architecture specifies how to produce shapes, not how to recognize them. Procedural grammars resist inversion because linguistic content and control structure are inseparable.

Hypothesis 2: The hidden cost. Bidirectionality has costs that are not visible at design time: KAMP is impractical, Strzalkowski is less efficient, GF requires architectural commitment. The benefit (+18% coverage) does not always justify the effort when a single direction suffices.

6. The Asymmetry is Structural, Not Accidental

The central thesis: the six dimensions of asymmetry (L15) are not resolvable technical problems. Each is independent of the others and irreducible:

D1 (complexity) is a consequence of the Chomsky hierarchy—it will not change with faster hardware.
D2 (ambiguity) stems from the mathematical properties of languages—no algorithm makes an inherently ambiguous language unambiguous (determinism, non-injectivity, and cardinality are a single phenomenon).
D3 (direction) reflects the logical order of derivation—the axiom precedes the terminals.
D4 (information) stems from Shannon’s architecture—the encoder knows the source, the decoder does not.
D5 (inference) is bounded by Gold.
D6 (temporality) is formalized by Hale/Levy.

Sidebar: LLMs do not solve asymmetry

Large language models seem to generate effortlessly—fluid text in linear time. But they shift the analytical cost rather than eliminating it. Training an LLM IS a massive act of analysis: compressing an entire corpus into model parameters. The O(n) generation cost per token is paid upfront by a colossal training cost. Intelligent generation always presupposes prior analysis.

7. Beyond NLP: Bioinformatics, Decompilation, and Music

Asymmetry manifests wherever formal grammars are used:

Bioinformatics. Stochastic context-free grammars (SCFG) predict RNA secondary structure—a recognition problem. The reverse direction—designing RNA sequences with a target structure—is inverse folding, known to be NP-hard. The asymmetry: folding (recognition, polynomial) vs. design (constrained generation, NP-hard).

Decompilation. In compilation, parsing (source code → AST) and code generation (AST → binary) are asymmetrical. Decompilation (binary → source code) is possible but produces code structurally different from the original—a manifestation of non-injectivity (D5): multiple source programs compile to the same binary.

Music. This is the “ideal laboratory”: musical composition (generation) and analysis have been established practices for centuries. Yet, most musical systems are unidirectional. The taxonomy below classifies major systems according to the directions they support:

→ See the chronological taxonomy in L13 Figure 1.

Analytical: GTTM (1983), computational Schenkerian analysis (2004), IDyOM (2018), melodic graph grammar (Finkensiep, 2019), grammatical compression (2021)
Formal Generative: Holtzman (1981), Max (1988), SuperCollider (1996), OpenMusic (1999), Euterpea (2013), TidalCycles (2014), L-systems (2021), CFG+Markov (2025)
Neural Generative: Jukebox (2020), MusicLM (2023), MusicGen (2023), Suno (2025)—no explicit grammar, deep learning only
Bidirectional—with varying degrees of integration: CCG jazz (Steedman, 1984 → 2014, 30 years between the two directions), EMI (Cope, 1989, sequential), OMax (2006), Antescofo (2008), unified voice-leading model (Harrison & Pearce, 2019), and BP3 (I2) = the most integrated case (PROD, ANAL, TEMP modes with the same grammar)

For details on each system, see L13 §8.

8. Inference: The Forgotten Third Direction

Beyond the generation-recognition duality, grammatical inference (L13 §9) constitutes a third direction that is even more fundamental—and even more neglected.

Gold (1967) proved that any “superfinite” class of languages (containing all finite languages and at least one infinite one) is not identifiable from positive data alone. This is a theoretical wall.

Horning (1969) found the first way out: PCFGs (Probabilistic Context-Free Grammars) are learnable in a Bayesian framework—by using prior knowledge (a “prior”) to discriminate between candidate grammars. The probabilistic prior breaks the symmetry exploited by Gold’s theorem.

Angluin’s L algorithm (1987) showed that regular languages are efficiently learnable—but with a membership oracle*, i.e., a recognition capability integrated into the inference process. Inference presupposes recognition, just as intelligent generation presupposes analysis.

The three operations form a hierarchy (L15):

$\underbrace{\text{Example-generation}}_{\mathcal{O}(n)} \;<\; \underbrace{\text{Recognition}}_{\mathcal{O}(n^\omega)} \;<\; \underbrace{\text{Inference}}_{2^{\mathcal{O}(n)}}$

(CFG recognition in $\mathcal{O}(n^\omega)$ , $\omega\approx2.37$ ; $$O(n^3)$$ with CYK.)

Precision (v2.1). This hierarchy holds only for unconstrained sub-problems. Generation under semantic constraints, however, becomes NP-complete—thus harder than recognition: this is the sign reversal (Kay 1996, Brew 1992), developed in L18. Asymmetry is therefore not a simple order of difficulty, but a differential coupling (L17).

Key Takeaways

Formal systems are mostly unidirectional: they perform either generation or analysis, rarely both.
Bidirectional systems (DCG, FST, GF, grammar inversion) have existed in NLP since the 1970s but have not been transferred to other fields.
Two main reasons: bidirectionality requires declarativity (separating the what from the how), and it has a hidden cost (impractical KAMP, less efficient inverted grammars).
Asymmetry is structural, not accidental: it stems from the Chomsky hierarchy, Parikh’s theorem, Shannon’s architecture—not from a lack of technical progress.
LLMs shift the analytical cost (toward training) but do not eliminate it.
Grammatical inference is the third direction, the most difficult, and it presupposes recognition (Angluin).
Music is the ideal laboratory for studying this asymmetry—BP3 being one of the few explicitly bidirectional systems.

Glossary

Bidirectionality: Property of a grammatical formalism that can be used for both generation (producing strings) and recognition (analyzing strings) with the same grammar.
DCG (Definite Clause Grammar): Grammatical extension of Prolog, inherently bidirectional thanks to unification, but with asymmetrical pathologies (different infinite recursions in each direction).
Declarativity: Property of a grammar that separates what it says (linguistic content) from how it is processed (direction, traversal strategy). A prerequisite for bidirectionality according to Appelt.
FST (Finite-State Transducer): A finite-state automaton with input and output. The inverse of an FST is also an FST—a property that does not generalize to context-free grammars.
GF (Grammatical Framework): Multilingual grammatical formalism by Ranta (2004, 2019) with abstract/concrete syntax separation, allowing parsing and generation in 40+ languages.
Grammar Inversion: Strzalkowski’s technique for automatically transforming a parsing grammar into a generation grammar by inverting the control structure. Proves that direction is embedded in procedural grammars.
KAMP: Appelt’s system unifying planning and realization in NLG. Bidirectional but “computationally impracticable.”
NLG (Natural Language Generation): Sub-field of NLP concerning text generation. The Reiter & Dale pipeline decomposes the process into document planning → microplanning → surface realization.
NLG Pipeline: Three-stage architecture (Reiter & Dale, 2000): 1) document planning (what to say), 2) microplanning (how to say it), 3) surface realization (the sentence). Structurally top-down.
Inverse Folding: In bioinformatics, the problem of designing an RNA sequence that folds into a target structure. NP-hard (Bonnet et al., 2020).
NLP (Natural Language Processing): The field of computer science dealing with natural language. In French: TAL (Traitement Automatique des Langues).

Prerequisites: L9, L13
Reading time: 14 min
Tags: #bidirectionality #reversible-grammars #NLP #GF #DCG #inference #Gold

← Return to index