Descriptive model theory classification of Counting hierarchy

Question

Descriptive model theory uses logic to characterize complexity classes

How to model

1. Counting Hierarchy
2. PSPACE

in descriptive model theory?

Answer 1

This is only a partial answer (to the $PSPACE$ characterization), but I don't have the reputation to comment.

$PSPACE$ has the following (equivalent) descriptive characterizations:

1. $FO[2^{n^{O(1)}}]$, first-order logic with exponentially iterated quantifier blocks.
2. $SO[n^{O(1)}]$, second-order logic with polynomially iterated quantifier blocks.
3. $SO[TC]$, second-order logic with a transitive closure operator.
4. $FO[PFP]$, first-order logic with a partial fixed point operator.
5. $CRAM$-$PROC[2^{n^{O(1)}}, n^{O(1)}]$, concurrent-read concurrent-write random access machine with exponential time and polynomial hardware.
6. $CRAM$-$PROC[n^{O(1)}, 2^{n^{O(1)}}]$, concurrent-read concurrent-write with polynomial time and exponential hardware.

These are all mentioned in Immerman's book Descriptive Complexity.

I can't find a reference on a descriptive characterization for the counting hierarchy, but here are some observations:

• $PP$ naturally corresponds to existential second-order logic with a second-order majority quantifier.

• $TC^0$ is equal to $FO$ with a majority quantifier. Padding arguments give us a relationship between $TC^0$ and $CH$. This relationship makes $SO$ with a majority quantifier (on relations) a natural candidate for a descriptive characterization of $CH$.