• 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?

  • $\begingroup$ What is the role of $G$ and $D$ in the questions? $\endgroup$
    – M.Monet
    Commented Jul 23, 2019 at 14:40
  • $\begingroup$ I've added some details to the problem spec to clarify. $\endgroup$ Commented Jul 23, 2019 at 16:21
  • $\begingroup$ The particular size definition could be varied to suit the responder. I'm making this problem up as I go along; it's not from a book. $\endgroup$ Commented Jul 23, 2019 at 16:26


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.