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 :
- SO[
] is equal to PSPACE it is also another way to write SO(TC) - SO[
] is equal to EXPTIME it is also another way to write SO(LFP)
More about...