> E.g., I've seen some people brag about some configuration language being easy to mechanically analyse because it's not Turing-complete, while in fact it's at least PSPACE-hard to analyse.

Isn't even just the question of minimising the length of a regular expression PSPACE-hard or so?