Complexity of certain decision problems about congruential languages

Given an arbitrary finite Church-Rosser Thue system S, it is shown that the question of whether a given congruence class is finite is undecidable, and the question of whether every congruence class is finite is not even semidecidable (it is complete for Pi-2). It is shown that the question of whether a given (resp., every) congruence class is a context-free language is at least as hard. Also, given a finite rewriting system over a commutative monoid, the question of whether every congruence class is finite is shown to be tractable. This contrasts with the known result that the question of whether a given congruence class is finite requires space at least exponential in the square root of the input length.