@inproceedings{10.1007/978-3-662-52921-8_15,
    author = {Anselm Haak and Heribert Vollmer},
    doi = {https://dx.doi.org/10.1007/978-3-662-52921-8_15},
    abstract = {We study the class {\$}{\$}{\backslash}mathrm {\{}{\backslash}{\\#}AC^0{\}}{\$}{\$}of functions computed by constant-depth polynomial-size arithmetic circuits of unbounded fan-in addition and multiplication gates. No model-theoretic characterization for arithmetic circuit classes is known so far. Inspired by Immerman's characterization of the Boolean class {\$}{\$}{\{}{\backslash}mathrm {\{}AC^0{\}}{\}}{\$}{\$}, we remedy this situation and develop such a characterization of {\$}{\$}{\backslash}mathrm {\{}{\backslash}{\\#}AC^0{\}}{\$}{\$}. Our characterization can be interpreted as follows: Functions in {\$}{\$}{\backslash}mathrm {\{}{\backslash}{\\#}AC^0{\}}{\$}{\$}are exactly those functions counting winning strategies in first-order model checking games. A consequence of our results is a new model-theoretic characterization of {\$}{\$}{\backslash}mathrm {\{}TC{\}}^0{\$}{\$}, the class of languages accepted by constant-depth polynomial-size majority circuits.},
    address = {Berlin, Heidelberg},
    booktitle = {Logic, Language, Information, and Computation},
    editor = {V{\"a}{\"a}n{\"a}nen, Jouko and Hirvonen, {\AA}sa and de Queiroz, Ruy},
    file = {A Model-Theoretic Characterization of Constant-Depth Arithmetic Circuits.pdf},
    isbn = {978-3-662-52921-8},
    pages = {234--248},
    publisher = {Springer Berlin Heidelberg},
    title = {{A Model-Theoretic Characterization of Constant-Depth Arithmetic Circuits}},
    year = {2016},
    date-added = {2022-07-01 15:21:37 +0200},
    date-modified = {2026-1-15 10:26:37 +0100}
}

@inproceedings{10.1007/978-3-662-52921-8_15, author = {Anselm Haak and Heribert Vollmer}, doi = {https://dx.doi.org/10.1007/978-3-662-52921-8_15}, abstract = {We study the class {\$}{\$}{\backslash}mathrm {{}{\backslash}{\#}AC^0{}}{\$}{\$}of functions computed by constant-depth polynomial-size arithmetic circuits of unbounded fan-in addition and multiplication gates. No model-theoretic characterization for arithmetic circuit classes is known so far. Inspired by Immerman's characterization of the Boolean class {\$}{\$}{{}{\backslash}mathrm {{}AC^0{}}{}}{\$}{\$}, we remedy this situation and develop such a characterization of {\$}{\$}{\backslash}mathrm {{}{\backslash}{\#}AC^0{}}{\$}{\$}. Our characterization can be interpreted as follows: Functions in {\$}{\$}{\backslash}mathrm {{}{\backslash}{\#}AC^0{}}{\$}{\$}are exactly those functions counting winning strategies in first-order model checking games. A consequence of our results is a new model-theoretic characterization of {\$}{\$}{\backslash}mathrm {{}TC{}}^0{\$}{\$}, the class of languages accepted by constant-depth polynomial-size majority circuits.}, address = {Berlin, Heidelberg}, booktitle = {Logic, Language, Information, and Computation}, editor = {V{\"a}{\"a}n{\"a}nen, Jouko and Hirvonen, {\AA}sa and de Queiroz, Ruy}, file = {A Model-Theoretic Characterization of Constant-Depth Arithmetic Circuits.pdf}, isbn = {978-3-662-52921-8}, pages = {234--248}, publisher = {Springer Berlin Heidelberg}, title = {{A Model-Theoretic Characterization of Constant-Depth Arithmetic Circuits}}, year = {2016}, date-added = {2022-07-01 15:21:37 +0200}, date-modified = {2026-1-15 10:26:37 +0100} }