Editing Descriptive complexity theory (section)

=== Second-order Krom formulae ===
On structures that have a successor function, NL can also be characterised by second-order [[Krom formula]]e.

SO-Krom is the set of Boolean queries definable with second-order formulae in [[conjunctive normal form]] such that the first-order quantifiers are universal and the quantifier-free part of the formula is in Krom form, which means that the first-order formula is a conjunction of disjunctions, and in each "disjunction" there are at most two variables. Every second-order Krom formula is equivalent to an existential second-order Krom formula.

SO-Krom characterises NL on structures with a successor function.<ref name=":2">Immerman 1999, p. 153{{Ndash}}4</ref>