L16) The Paradox of Bidirectionality

50 Years of Forgotten Reversible Grammars

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

Where does this article fit in?

In L13, we saw that some 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 its mathematical foundations.

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

Why is this important?

Imagine a machine translator that can only translate from French to English, never the other way around. And you’re 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 domains. In bioinformatics, grammars predict RNA structure (parsing) 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 domains, because bidirectionality requires declarativity — and most applied grammars are procedural.

Let’s explain step by step

1. The landscape map: who does what?

Let’s start by taking inventory. Formal systems can be classified 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 asymmetric pathologies (DCG) or impractical cost (KAMP).*

Three observations immediately stand out:

Most systems are unidirectional. They either perform 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) has 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 intrinsically 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 (FSTs), 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 inverse (parsing).

Koskenniemi’s two-level morphology (1983) directly exploits this. But this inversion property applies only to 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: bidirectionality at scale

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

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

The same abstract tree can be linearized (generation: tree → phrase) or parsed (recognition: phrase → 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 impractical

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 impractical.” 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 scratch, 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 entirely resist inversion. The very fact that an inversion process is necessary proves 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 declarativity prerequisite. Appelt said it: bidirectionality requires declarative grammars — which state what without stating how. However, most applied grammars are procedural: they integrate the processing direction into the grammar itself. A grammar of forms in architecture specifies how to produce forms, 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 the design stage: KAMP impractical, Strzalkowski less efficient, GF requiring architectural commitment. The benefit (+18% coverage) does not always justify the effort when only one direction is sufficient.

6. Asymmetry is structural, not accidental

The central thesis: the six dimensions of asymmetry (L15) are not solvable 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 intrinsically 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

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 eliminate 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 inverse 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 asymmetric. 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 the main 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, only deep learning
Bidirectional — with highly variable 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, even more fundamental — and even more neglected — direction.

Gold (1967) proved that any “superfinite” class of languages (containing all finite languages and at least one infinite) 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 within 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{Generation}}_{\mathcal{O}(n)} \;<\; \underbrace{\text{Recognition}}_{\mathcal{O}(n^3)} \;<\; \underbrace{\text{Inference}}_{2^{\mathcal{O}(n)}}$

Key takeaways

Formal systems are predominantly unidirectional: they either perform generation or parsing, rarely both.
Bidirectional systems (DCG, FST, GF, grammar inversion) have existed in NLP since the 1970s but have not been transferred to other domains.
Two main reasons: bidirectionality requires declarativity (separating the what from the how), and it has a hidden cost (KAMP impractical, inverted grammars less efficient).
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 (towards training) but do not eliminate it.
Grammatical inference is the third, most difficult direction, and it presupposes recognition (Angluin).
Music is the ideal laboratory for studying this asymmetry — BP3 being one of the rare explicitly bidirectional systems.

Glossary

Bidirectionality: Property of a grammatical formalism that can be used for both generation (producing strings) and recognition (parsing strings) with the same grammar.
DCG (Definite Clause Grammar): Grammatical extension of Prolog, intrinsically bidirectional thanks to unification, but with asymmetric pathologies (different infinite recursions in each direction).
Declarativity: Property of a grammar that separates what it says (the linguistic content) from how it is processed (the direction, the traversal strategy). A prerequisite for bidirectionality according to Appelt.
FST (Finite-State Transducer): 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): Ranta’s multilingual grammatical formalism (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 integrated into procedural grammars.
KAMP: Appelt’s system unifying planning and realization in NLG. Bidirectional but “computationally impractical.”
NLG (Natural Language Generation): Subfield of NLP concerned with text generation. Reiter & Dale’s pipeline breaks down 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 that deals 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

← Back to index