Class Description
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)
Linked From
No class.