Details wanted on the reduction from Circuit Value to CFG Membership

Question

Consider a Boolean Circuit $C$ which takes $n$ inputs and has one output. Notation: Let $\textit{size}(C)$ be the size of circuit $C$: the total number of gates in $C$. Let $G = (V,\Sigma,R,S)$ be a context-free grammar where $V$ is the set of non-terminals. Circuit-Value is the circuit value problem, and CFGM is the context-free grammar membership problem. Let $c$ and $k$ be constants.

EDIT: For this question, let's say that a context-free grammar $G$ is recursive if there is some $N \in V$ and some sequence of derivations from $R$ such that $N \rightarrow^* \cdots N \cdots$, that is, where $N$ appears on the right-hand side of a derivation from $N$. If there is no such $N$, let's call $G$ non-recursive.

Since CFGM is a P-Complete problem, there is a reduction from Circuit-Value to CFGM. So we can run $C$ through the reduction to get a context-free grammar G. In the questions below, we assume that $\textit{size}(C) = O(n^c)$, that is, the size of $C$ is polynomial in $n$.

Two questions arise since the reductions I've seen (EDIT: here and here) don't address these directly:

1. Is $|V| = O(n^k)$? That is, is $|V|$ polynomial in $n$?
2. Is $G$ non-recursive?

Answer 1

In the Circuit Value Problem the task is to evaluate a Boolean circuit with given input values. The circuit can be modelled as a directed acyclic graph. The inputs have no incoming edges, the other nodes represent Boolean gates. Here we will assume the gates are AND, OR and NOT, and we also assume these gates are binary (unary for NOT).

We start with monotone circuits, where the connection to context-free grammars is rather direct. In a monotone circuit we have no NOT gates. (Every circuit is easily translated in a monotone circuit, using De Morgan's rules, pushing the negations down to the inputs.)

For each node in the circuit (inputs and gates) we set a unique variable for the CFG. If AND gate $A$ has inputs $B$ and $C$, then production $A\to BC$ simulates AND: $A$ only generates a string if both $B$ and $C$ do. Likewise productions $A\to B$, $A\to C$ simulate OR. Then for the inputs, only if input $I$ is evaluated TRUE we introduce production $I\to \varepsilon$. Finally we choose the output-gate variable $S$ as axiom for the grammar. Now for each variable $A\Rightarrow^* \varepsilon$ iff gate/input $A$ evaluates to TRUE. In particular this holds for $S$.

This is Problem A.7.4 "Context-Free Grammar $\varepsilon$-Membership" from your linked document "A Compendium of Problems Complete for P". The authors have extended this to a book "Limits to Parallel Computation: P-Completeness Theory" (1995).

(1) As we can see, the number of variables in the grammar equals the number of "nodes" in the circuit, i.e., inputs and gates.

(2) Productions run "backwards" in the circuit (from output gate to inputs). As the circuit is acyclic, no variable derives itself, i.e., the grammar is non-recursive in your terminology.

We can extend this to circuits that include NOT. For this we take two copies of each variable: $A^0$ and $A^1$, with the intended meaning that $A^v\Rightarrow^* \varepsilon$ iff input/gate $A$ evaluates to TRUE (when $v=1$) or evaluates to FALSE (when $v=0$). Starting with the inputs, we have production $I^1\to \varepsilon$ if $I$ evaluates TRUE (respectively, $I^0\to \varepsilon$ when $I$ evaluates FALSE).

The productions again model the gates. For AND gate $A$ with inputs $B,C$ we have four produtions $A^{u\land v}\to B^u C^v$ for $u,v\in \{0,1\}$. Similarly for OR gates $A^{u\lor v}\to B^u C^v$. And of course, for a NOT gate $A$ with input $B$ we get two productions $A^{\lnot v}\to B^v$ for $v\in \{0,1\}$. The circuit evaluates to TRUE iff the grammar generates $\varepsilon$ if we take $S^1$ as axiom.