pith. sign in

arxiv: 1906.11752 · v1 · pith:V2JMRMTSnew · submitted 2019-06-27 · 💻 cs.CL · cs.LO

Semantic expressive capacity with bounded memory

Antoine Venant , Alexander Koller This is my paper

Pith reviewed 2026-05-25 14:48 UTC · model grok-4.3

classification 💻 cs.CL cs.LO
keywords semantic parsingprojective mechanismsbounded memorycompositional semanticsexpressive capacitygrammar-based systemsneural semantic parsers
0
0 comments X

The pith

Syntactically projective mechanisms require unbounded memory to represent certain semantic relations.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that mechanisms enforcing syntactic projectivity must track an unbounded number of locations in semantic representations for some sentence-meaning relations. Nonprojective mechanisms can represent the same relations using only bounded memory. This result is relevant to both grammar-based parsers and neural models for semantic parsing. It shows a fundamental difference in expressive capacity tied to the projectivity constraint. The distinction helps explain memory requirements in compositional semantic systems.

Core claim

In order to represent certain relations, mechanisms which are syntactically projective must be able to remember an unbounded number of locations in the semantic representations, where nonprojective mechanisms need not.

What carries the argument

Syntactic projectivity, a constraint on how semantic attachments align with sentence order without crossings, which forces the mechanism to maintain memory of multiple unresolved semantic positions.

If this is right

  • Projective grammar formalisms cannot achieve full expressivity for these relations with bounded memory.
  • Neural architectures incorporating projective biases may require additional memory resources for complex semantics.
  • Nonprojective mechanisms provide an alternative that maintains expressivity without increasing memory bounds.
  • Both grammar-based and neural semantic parsing systems are affected by this memory distinction.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Parser designers could explore nonprojective components to lower memory usage in semantic tasks.
  • The result invites empirical tests on whether common semantic relations in language require the unbounded memory that projectivity demands.
  • Hybrid parsing systems might adaptively choose projective or nonprojective strategies to optimize memory.

Load-bearing premise

There exist relations between sentences and semantic representations for which the projective constraint on the parsing mechanism forces it to remember an unbounded number of locations.

What would settle it

Demonstrating a syntactically projective mechanism that represents all such relations using only a fixed, finite amount of memory.

Figures

Figures reproduced from arXiv: 1906.11752 by Alexander Koller, Antoine Venant.

Figure 1
Figure 1. Figure 1: (a) Nonprojective and (b) projective analysis. [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Semantic construction with TAG: (a) TAG derivation, (b) derivation tree, (c) derived tree, (d) semantic [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: The CSD graph for ((2), (1, 0), (1), (0, 0)); blocks indicated by gray boxes. contrast, a homomorphic interpretation of the pro￾jective tree (c) has to use at least four sources, as the intermediate result in (e) illustrates. 4 Projective cross-serial dependencies We will now investigate the ability of projec￾tive grammar formalisms (G, Hk) to express L(TAG, H2). We will define a relation CSD ∈ L(TAG, H2) … view at source ↗
Figure 4
Figure 4. Figure 4: An derivation of ((0), (0,0), (0), (0,0)). [PITH_FULL_IMAGE:figures/full_fig_p006_4.png] view at source ↗
read the original abstract

We investigate the capacity of mechanisms for compositional semantic parsing to describe relations between sentences and semantic representations. We prove that in order to represent certain relations, mechanisms which are syntactically projective must be able to remember an unbounded number of locations in the semantic representations, where nonprojective mechanisms need not. This is the first result of this kind, and has consequences both for grammar-based and for neural systems.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper proves that syntactically projective mechanisms for compositional semantic parsing must remember an unbounded number of locations in semantic representations to capture certain sentence-to-semantics relations, whereas nonprojective mechanisms need not; this is shown via an existence proof and has implications for both grammar-based and neural systems.

Significance. If the central existence proof holds, the result supplies a parameter-free separation between projective and nonprojective mechanisms on memory lower bounds. This is the first result of its kind and directly informs the design of semantic parsers by identifying a formal cost of the projectivity constraint.

minor comments (3)
  1. [Abstract / Introduction] The abstract states the existence of a proof but the manuscript should include an explicit high-level outline of the separating relations and the memory model in the introduction to make the claim immediately verifiable.
  2. [Preliminaries] Notation for 'locations in the semantic representations' and the precise definition of bounded vs. unbounded memory should be introduced with a small example before the main theorem.
  3. [Discussion] The consequences for neural systems are mentioned but not developed; a short paragraph contrasting the result with known RNN or Transformer memory analyses would strengthen the discussion.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the paper, recognition of its significance as the first result of this kind, and recommendation for minor revision. No specific major comments were provided in the report.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper presents a mathematical existence proof separating the memory requirements of syntactically projective versus nonprojective mechanisms for certain sentence-to-semantics relations. No self-definitional steps, fitted inputs renamed as predictions, or load-bearing self-citation chains are present; the result is parameter-free and concerns only the existence of separating relations under standard definitions of projectivity and memory. The derivation is therefore self-contained.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Review is based solely on the abstract; no free parameters, invented entities, or specific axioms beyond standard domain concepts are mentioned.

axioms (1)
  • domain assumption Syntactic projectivity and nonprojectivity are well-defined properties of parsing mechanisms that directly constrain memory use over semantic representations.
    The proof distinction rests on these concepts as invoked in the abstract.

pith-pipeline@v0.9.0 · 5574 in / 1160 out tokens · 56709 ms · 2026-05-25T14:48:25.164936+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

12 extracted references · 12 canonical work pages

  1. [1]

    In Proceedings of the COLING Work- shop on Grammar Engineering and Evaluation

    The Grammar Matrix: An open-source starter-kit for the rapid development of cross- linguistically consistent broad-coverage precision grammars. In Proceedings of the COLING Work- shop on Grammar Engineering and Evaluation. Patrick Blackburn and Johan Bos. 2005. Represen- tation and Inference for Natural Language . CSLI Publications. Johan Bos. 2008. Wide-...

    work page 2005

  2. [2]

    In Proceedings of the 39th ACL

    An algebra for semantic construction in constraint-based grammars. In Proceedings of the 39th ACL. Bruno Courcelle and Joost Engelfriet. 2012. Graph Structure and Monadic Second-Order Logic, a Lan- guage Theoretic Approach. Cambridge University Press. Mary Dalrymple, John Lamping, Fernando C. N. Pereira, and Vijay Saraswat. 1995. Linear logic for meaning ...

    work page 2012

  3. [3]

    In Proceedings of the 15th EACL

    An incremental parser for Abstract Meaning Representation. In Proceedings of the 15th EACL. Frank Drewes, Hans-J¨org Kreowski, and Annegret Ha- bel. 1997. Hyperedge replacement graph gram- mars. In G. Rozenberg, editor, Handbook of Graph Grammars and Computing by Graph Transforma- tion, pages 95–162. World Scientific. Chris Dyer, Adhiguna Kuncoro, Miguel B...

    work page 1997

  4. [4]

    In Proceedings of ACL

    Global transition-based non-projective depen- dency parsing. In Proceedings of ACL. Aravind K. Joshi and Yves Schabes. 1997. Tree- Adjoining Grammars. In G. Rozenberg and A. Salo- maa, editors, Handbook of Formal Languages, vol- ume 3. Springer-Verlag. Stephan Kepser and James Rogers. 2011. The equiva- lence of tree adjoining grammars and monadic linear c...

    work page 1997

  5. [5]

    In Proceed- ings of the 19th Conference on Computational Lan- guage Learning

    A synchronous hyperedge replacement gram- mar based approach for AMR parsing. In Proceed- ings of the 19th Conference on Computational Lan- guage Learning. William Rounds. 1969. Context-free grammars on trees. In Proceedings of the First Annual ACM Sym- posium on Theory of Computing (STOC). Stuart M. Shieber. 1985. Evidence against the context- freeness o...

    work page 1969

  6. [6]

    yd(C2)∈{⟨,⟩}∗ and yd(C4)∈{⟨,x,⟩}∗

    work page

  7. [7]

    3.| yd(t5)|z = 0 for anyz∈{a,b,c,d } Proof

    Either left(C4) ∈ {x}∗ and| left(C3)|z = 0 for any z∈{ a,b,c,d }, or symmetrically, right(C4)∈{ x}∗ and| right(C3)|z = 0 for anyz∈{a,b,c,d }. 3.| yd(t5)|z = 0 for anyz∈{a,b,c,d } Proof. First point: Lets = left(C1) andn0 = |s|⟨. Let y ∈ {a,b,c,d} and assume y ∈ left(C2). Pumping C2-C4 n0 + 1-times yields a tree tn0+1 ∈ T such that s· left(C2)n0+1 is a pre...

    work page

  8. [8]

    For some (i,j )∈{ (2, 4), (4, 2)}, left(Ci)∈ X+, right(Ci) ∈ Y +, left(Cj) ∈ X∗ and right(Cj)∈Y∗

    work page

  9. [9]

    left(C2)∈ A+, right(C2)∈ D+, left(Cj)∈ B+ and right(Cj)∈C+

    work page

  10. [10]

    Either left(C2) ∈ X+, right(C2) = ϵ and left(C4)· right(C4)∈ Y +, or symmetrically left(C2) = ϵ, right(C2)∈Y + and left(C4)· right(C4)∈X+. Proof. All these observations follow easily from the first point of Lemma 10 (governing the rela- tive number of occurrences of a,c -tokens on one hand andb,d -tokens on the other hand), projectiv- ity, and the followin...

    work page

  11. [11]

    Case 1 Consider first the case where Lemma 11 applies i.e

    We distinguish cases according to Lem- mas 11 and 12. Case 1 Consider first the case where Lemma 11 applies i.e. C2 andC4 generate only one kind of bar token, z, and brackets. We now distinguish cases depending on the value ofz. Before this, we emphasize that in all subcases it holds that nt x = nt′ x . subcase i) z ̸= y. Since all nodes of t′ 0 are contai...

    work page

  12. [12]

    Hence, in the case where t0 overlaps with C2, t0 contains all nodes of C2 andC4

    does not generatey-tokens. Hence, in the case where t0 overlaps with C2, t0 contains all nodes of C2 andC4. Since t0 also contains all nodes of t′ 0, et0 ≥ et′ 0 +eC2[C4] = et′ 0 +nt y−nt′ y . Moreover, rt y≥ rt′ y . We can then conclude using inequation 3. Consider now the case where t0 does not over- lap withC2 orC4. Since ally-tokens are generated by t...

    work page