Given
- an LSTM $N$ of a given size $A$,
- a sentence $S$ with a given number of words $B$,
- a Chomsky grammar hierarchy level $C$ in 0-3,
- a Chomsky grammar $G$ of level $C$ of size $D$,
A given fixed, concrete grammar $G$ defines a set of sentences $S$ which have the structure described by the grammar. The size parameter $D$ gives a bound on the complexity of $G$. Let's use the definition of an unrestricted grammar $G = (V, \Sigma, P, S)$, where
- $V$ is a set of nonterminal symbols
- $\Sigma$ is a set of terminal symbols
- $P$ is a set of production rules and
- $S$ is a set of start symbols in $V$
For our size measure $D$ we can adopt a simple rule such as $D=|V|+|\Sigma|+|P|$ where $|Q|$ is the number of elements in set $Q$.
Assume that the input to $N$ is a vector of size $B$ of integers representing words of $S$, and the output of $N$ is a single binary category with value 1 for $S$ in $G$ and 0 otherwise, and that the node weights of $N$ have been adjusted to optimally perform the recognition task. In practice this would be through a labelled training process. Let's assume that we have an oracle that gives us an optimal assignment of node weights. The neural network architecture together with its size parameters (number of layers, number of nodes per layer and so on), together with the constant weights assigned to the nodes, comprise together a particular kind of computer program which operates in a fixed and well understood way. In particular it is a kind of dataflow computation graph with some constant inputs, some variable inputs, some outputs and some feedback of certain node outputs as node inputs. Once it has been configured, it operates in a deterministic and completely defined way.
Q1. Can $N$ recognize sentences (accept or reject) $S$?
Q2. Is this a problem in Theoretical Computer Science?
Q3. If the Chomsky Hierarchy is too old-fashioned, can you work this problem for the Complexity Zoo?
