Semantic expressive capacity with bounded memory
This foundational result impacts both grammar-based and neural systems in natural language processing by revealing memory constraints in semantic parsing.
The paper tackled the problem of compositional semantic parsing mechanisms needing unbounded memory for certain relations, proving that syntactically projective mechanisms require unbounded memory while nonprojective ones do not, with this being the first such result.
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.