<p>The answer to all three questions is negative. Consider e.g. the prefix version (3), and assume for contradiction that it is decidable by a (wlog deterministic) automaton $A$ with $m$ states. Consider the strings</p>

<p>$$\begin{align}
u_k&amp;={+}^{m-k}{*}{+}^k,\\
v_l&amp;=1^{l+1}0^{m-l+1}.
\end{align}$$</p>

<p>Notice that $u_kv_l$ is a well-formed Boolean sentence for every $0\le k\le m$, $0\le l\le m+1$, and it is easy to see that $u_kv_l$ evaluates to $1$ iff $k&lt;l$. By the pigeonhole principle, there are $0\le k&lt;l\le m$ such that $u_k$ and $u_l$ land in the same state of $A$, thus $u_kv_l$ and $u_lv_l$ are both accepted or both rejected. However, the former evaluates to $1$, and the latter to $0$.</p>

<p>For infix formulas (questions 1,2), one can use in a similar way formulas of the form</p>

<p>$$(0+((0+\cdots((0+((1+((0+\cdots((0+0)*1))*1))\dots*1))*0))*1))\dots*1)).$$</p>

<p>The argument in fact shows that any deterministic automaton evaluating well-formed Boolean sentences of length $n$ must have size $\Omega(n)$, or in other words, any online algorithm for evaluation of such sentences needs space at least $\Omega(\log n)$. This bound is tight: as shown by <a href="http://www.math.ucsd.edu/~sbuss/ResearchWeb/Boolean3/index.html" rel="nofollow">Buss</a>, it is possible to evaluate Boolean sentences in infix notation in online space $O(\log d)$, where $d$ is the depth of the formula (i.e., maximum nesting of brackets). (The paper advertises it as an online $O(\log\log n)$-space algorithm for evaluation of <em>balanced</em> formulas, using the fact that these have depth $d=\log n$.)</p>

<p>On the other hand, as also shown by Buss, Boolean sentence evaluation (in either prefix or infix notation) can be done in ALOGTIME, aka uniform $\mathrm{NC}^1$, and it is in fact complete for this class under DLOGTIME many-one reductions. Since regular languages with unsolvable syntactic monoid (for example, $\bigl((a|b)^3(ab^*a|b)\bigr)^*$) are also $\mathrm{NC}^1$-complete, it follows that one can <em>reduce</em> Boolean sentence evaluation in DLOGTIME to a regular language.</p>

CC BY-SA 3.0
2014-12-20T20:19:06.827Z
2014-12-20T21:12:14.770Z
2014-12-20T21:12:14.770Z
Emil Jeřábek
<p>Let's define two CFGs: </p>

<pre><code>S  ::= 0 | 1 | (S+S) | (S*S)  
S' ::= 0 | 1 |  S+S  |  S*S  | (S)
</code></pre>

<p>And two languages:</p>

<p>M  = { w | S  generates w, and w evaluates to 1 }<br>
M' = { w | S' generates w, and w evaluates to 1 }</p>

<p>In both cases, evaluating is done by interpreting + as logical or, * as logical and, and in the case of M' by being careful about * having higher precedence than +.</p>

<p><strong>Suppose w is in S, and u is in S'</strong>. My questions are:</p>

<ol>
<li>Is there a finite automaton (or a regex) that can decide wheter w is in M?</li>
<li>Is there a finite automaton (or a regex) that can decide wheter u is in M'?</li>
<li>Suppose S ::= 0 | 1 | +SS | *SS. (Prefix notation) Does this change the answer to question 1?</li>
</ol>

<p>I'm aware that without knowing whether w is in S, deciding if w is in M isn't solvable by finite automata due to pumping lemma (we'd have an issue with parentheses), similarly for u, S' and M'. However, knowing that w is in S (and u is in S') might make the problem significantly easier. </p>

<p>Note: if the answer is yes, please write the grammar/regex/proof sketch/explanation in spoiler tags. :)</p>

<regular-language><boolean-formulas>
What is the complexity of the set of closed boolean tautologies assuming well formed formulae?
Luka Mikec
# What is the complexity of the set of closed boolean tautologies assuming well formed formulae?

(Asked by: username_0 on 2014-12-20)

Let's define two CFGs: 
S  ::= 0 | 1 | (S+S) | (S*S)  
S' ::= 0 | 1 |  S+S  |  S*S  | (S)

And two languages:
M  = { w | S  generates w, and w evaluates to 1 }
M' = { w | S' generates w, and w evaluates to 1 }
In both cases, evaluating is done by interpreting + as logical or, * as logical and, and in the case of M' by being careful about * having higher precedence than +.
Suppose w is in S, and u is in S'. My questions are:

Is there a finite automaton (or a regex) that can decide wheter w is in M?
Is there a finite automaton (or a regex) that can decide wheter u is in M'?
Suppose S ::= 0 | 1 | +SS | *SS. (Prefix notation) Does this change the answer to question 1?

I'm aware that without knowing whether w is in S, deciding if w is in M isn't solvable by finite automata due to pumping lemma (we'd have an issue with parentheses), similarly for u, S' and M'. However, knowing that w is in S (and u is in S') might make the problem significantly easier. 
Note: if the answer is yes, please write the grammar/regex/proof sketch/explanation in spoiler tags. :)

**Tags:** regular-language, boolean-formulas

---

## 1 answers

### Answer by username_1 on 2014-12-20. Score: 3 | Accepted answer

The answer to all three questions is negative. Consider e.g. the prefix version (3), and assume for contradiction that it is decidable by a (wlog deterministic) automaton $A$ with $m$ states. Consider the strings

$$\begin{align}
u\_k&={+}^{m-k}{\*}{+}^k,\\
v\_l&=1^{l+1}0^{m-l+1}.
\end{align}$$

Notice that $u\_kv\_l$ is a well-formed Boolean sentence for every $0\le k\le m$, $0\le l\le m+1$, and it is easy to see that $u\_kv\_l$ evaluates to $1$ iff $k

For infix formulas (questions 1,2), one can use in a similar way formulas of the form

$$(0+((0+\cdots((0+((1+((0+\cdots((0+0)\*1))\*1))\dots\*1))\*0))\*1))\dots\*1)).$$

The argument in fact shows that any deterministic automaton evaluating well-formed Boolean sentences of length $n$ must have size $\Omega(n)$, or in other words, any online algorithm for evaluation of such sentences needs space at least $\Omega(\log n)$. This bound is tight: as shown by [Buss](http://www.math.ucsd.edu/~sbuss/ResearchWeb/Boolean3/index.html), it is possible to evaluate Boolean sentences in infix notation in online space $O(\log d)$, where $d$ is the depth of the formula (i.e., maximum nesting of brackets). (The paper advertises it as an online $O(\log\log n)$-space algorithm for evaluation of *balanced* formulas, using the fact that these have depth $d=\log n$.)

On the other hand, as also shown by Buss, Boolean sentence evaluation (in either prefix or infix notation) can be done in ALOGTIME, aka uniform $\mathrm{NC}^1$, and it is in fact complete for this class under DLOGTIME many-one reductions. Since regular languages with unsolvable syntactic monoid (for example, $\bigl((a|b)^3(ab^\*a|b)\bigr)^\*$) are also $\mathrm{NC}^1$-complete, it follows that one can *reduce* Boolean sentence evaluation in DLOGTIME to a regular language.


---

