Monadic second-order logic with cardinality predicates
The problem concerns the extension of Monadic Second Order Logic (over a binary relation representing the edge relation) with the following atomic formulas:
where is a fixed recursive set of integers.
Let us fix and a closed formula in this language.
* indicates original appearance(s) of problem.