grammatical complexity of propositional and monadic predicate validities? (and grammars for recursive but not context-sensitive languages?)
There is a linear space deterministic algorithm for deciding whether a given propositional formula is tautological. The algorithm goes over all truth assignments and verifies that the formula evaluates to TRUE under all of them.

Regarding monadic predicate logic, Lewis (journal version) determined that the nondeterministic time complexity is $2^{\Theta(n/\log n)}$, but I'm not sure if the nondeterministic space complexity is known. Perhaps you could sift through the papers citing Lewis.