Class Description

FO(DTC): First-order with deterministic transitive closure

FO(DTC) is defined as FO(tc) where the transitive closure operator is deterministic, which means that when we apply DTC(${\displaystyle {\varphi }_{u,v}}$), we know that for all ${\displaystyle u}$, there exist at most one ${\displaystyle v}$ such that phi(u,v).

We can suppose that DTC(${\displaystyle {\varphi }_{u,v}}$) is syntactic sugar for TC(${\displaystyle {\psi }_{u,v}}$) where ${\displaystyle \psi (u,v)=\varphi (u,v)\wedge \mathrm{\forall }x,(x=v\vee \mathrm{\neg }\psi (u,x))}$.

It was shown in [Imm98] on page 144 that this class is equal to L.

Linked From 1 Classes

L: Logarithmic Space

The class of decision problems solvable by a Turing machine restricted to use an amount of memory logarithmic in the size of the input, n. (The input itself is not counted as part of the memory.)

L is contained in P. L contains NC¹ [Bor77], and is contained in generalizations including NL, L/poly, SL, RL, ⊕L, and Mod_kL.

Reingold [Rei04] showed that, remarkably, L = SL. In other words, undirected graph connectivity is solvable in deterministic logarithmic space.

Immerman [Imm83] showed that L is the class FO(dtc) of first-order expressible queries with a deterministic transitive closure.

L queries are exactly the one that can be written in a syntactic restriction of While languages.

More about...