__Research article:__

** Samuel R. Buss.
"The Boolean formula value problem is in ALOGTIME."
In **

** Download article: postscript or PDF. **

** Abstract: **The Boolean formula value problem is in
alternating log time and, more generally, parenthesis context-free languages are in
alternating log time. The evaluation of reverse Polish notation Boolean formulas is also
in alternating log time. These results are optimal since the Boolean formula value problem
is complete for alternating log time under deterministic log time reductions.
Consequently, it is also complete for alternating log time under AC^{0}
reductions.