Model-Theoretic Characterizations of Boolean and Arithmetic Circuit Classes of Small Depth

Arnaud Durand, Anselm Haak, Heribert Vollmer

In this paper we give a characterization of both Boolean and arithmetic circuit classes of logarithmic depth in the vein of descriptive complexity theory, i.e., the Boolean classes…