1
$\begingroup$

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?
$\endgroup$
5
  • $\begingroup$ @HendrikJan: Thanks for writing. I’ve added an edit to address your question. I’ll work on your other question shortly. $\endgroup$
    – ShyPerson
    Aug 10, 2021 at 0:33
  • $\begingroup$ @HendrikJan: I've added an edit to include two references to the reductions I discuss. $\endgroup$
    – ShyPerson
    Aug 10, 2021 at 0:47
  • 1
    $\begingroup$ Thanks for the references. As far as I understand both of them mention a reduction from the abstract problem GEN which simulates a binary operation to CFGM. Also Problem A7.4 in the TR "Compendium" is like the one I sketched above. Indeed it uses MonotoneCVP. The goal is to generate the empty string by the grammar. In this formulation the number of variables equals the number of vertices in the circuit: that must be equal to the number of inputs plus the number of gates. As the gates are binary, the total number of variables is linear in the number of gates. $\endgroup$ Aug 10, 2021 at 23:20
  • $\begingroup$ @HendrikJan: Thanks for addressing my first question. As for my second question, can we conclude that since each gate in the circuit is distinct, then every non-terminal in the CFG is distinct, thereby making the CFG non-recursive? $\endgroup$
    – ShyPerson
    Aug 11, 2021 at 3:25
  • $\begingroup$ Ah, I now see you also have added the definition of recursive. (I was mixed up with the notion of recursiveness related to computability.) Yes, your hunch is right. $\endgroup$ Aug 11, 2021 at 21:52

1 Answer 1

1
+50
$\begingroup$

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.