Class Description

SO[TC]: Second-Order logic with transitive closure

SO[TC] is to SO as FO[TC] is to FO. The TC operator can now also take second-order variable as argument.

In Descriptive complexity we can see thatSO[TC] is equal to PSPACE.

Linked From

SO[]: Iterated Second-Order logic

SO[] is to SO as FO[] is to FO. But we now also have second-order quantifier in the quantifier block.

In Descriptive complexity we can see that :

More about...