4 ms·

I'm having trouble reconciling your first and second paragraphs. The first paragraph states that program analysis is PSPACE complete in the size of the program

I'm having trouble reconciling your first and second paragraphs. The first paragraph states that program analysis is PSPACE complete in the size of the program while the second appears to be saying that it is EXPTIME. But it is not known that PSPACE = EXPTIME. Could you please clarify this point ?

pron 6y ago
In the first paragraph I mentioned that a specific, very simple FSM language is PSPACE, and in the second paragraph I was talking about terminating languages in general, and didn't mention EXPTIME. For more elaborate terminating languages, the complexity of analysis is much, much bigger than EXPTIME.