Thomas R. Puzak, A. Hartstein, et al.
CF 2007
We show that the elementary theory of Boolean algebras is ≤log-complete for the Berman complexity class {n-ary union}c<ω STA(, 2cn, n), the class of sets accepted by alternating Turing machines running in time 2cn for some constant c and making at most n alternations on inputs of length n; thus the theory is computationally equivalent to the theory of real addition with order. We extend the completeness results to various subclasses of Boolean algebras, including the finite, free, atomic, atomless, and complete Boolean algebras. Finally we show that the theory of any finite collection of finite Boolean algebras is complete for PSPACE, while the theory of any other collection is ≤log-hard for {n-ary union}c<ω STA(, 2cn, n). © 1980.
Thomas R. Puzak, A. Hartstein, et al.
CF 2007
Zohar Feldman, Avishai Mandelbaum
WSC 2010
Heinz Koeppl, Marc Hafner, et al.
BMC Bioinformatics
Renu Tewari, Richard P. King, et al.
IS&T/SPIE Electronic Imaging 1996