• 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
    Jul 23 '19 at 14:40
  • $\begingroup$ I've added some details to the problem spec to clarify. $\endgroup$ Jul 23 '19 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$ Jul 23 '19 at 16:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.