Editing Descriptive complexity theory (section)

=== Transitive closure logic ===
First-order logic gains substantially in expressive power when it is augmented with an operator that computes the transitive closure of a binary relation. The resulting [[transitive closure logic]] is known to characterise [[NL (complexity)|non-deterministic logarithmic space (NL)]] on ordered structures. This was used by [[Neil Immerman|Immerman]] to show that NL is closed under complement (i. e. that NL = co-NL).<ref>{{Cite journal|last=Immerman|first=Neil|date=1988|title=Nondeterministic Space is Closed under Complementation|url=http://dx.doi.org/10.1137/0217058|journal=[[SIAM Journal on Computing]]|volume=17|issue=5|pages=935–938|doi=10.1137/0217058|issn=0097-5397}}</ref>

When restricting the transitive closure operator to [[Fixed-point logic#Deterministic transitive closure logic|deterministic transitive closure]], the resulting logic exactly characterises [[L (complexity)|logarithmic space]] on ordered structures.