Editing Descriptive complexity theory (section)

=== FO without any operators ===

In [[circuit complexity]], first-order logic with arbitrary predicates can be shown to be equal to [[AC0|AC<sup>0</sup>]], the first class in the [[AC (complexity)|AC]] hierarchy. Indeed, there is a natural translation from FO's symbols to nodes of circuits, with <math>\forall, \exists</math> being <math>\land</math> and <math>\lor</math> of size {{mvar|n}}. First-order logic in a signature with arithmetical predicates characterises the restriction of  the AC<sup>0</sup> family of circuits to those constructible in [[LH (complexity)|alternating logarithmic time]].<ref name="Immerman 1999, p. 86"/> First-order logic in a signature with only the order relation corresponds to the set of [[star-free language]]s.<ref>{{Cite book|last=Robert.|first=McNaughton|url=http://worldcat.org/oclc/651199926|title=Counter-free automata|date=1971|publisher=M.I.T. Press|isbn=0-262-13076-9|oclc=651199926}}</ref><ref>Immerman 1999, p. 22</ref>