Research article:

    Samuel R. Buss.
    "The Boolean formula value problem is in ALOGTIME."
    In Proceedings of the 19th Annual ACM Symposium on Theory of Computing (STOC'87), 1987, pp. 123-131.

    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 AC0 reductions.