In fact, this problem was shown to be EXPSPACE-hard years before it was shown to be decidable at all (Mayr, 1981).
למעשה, בעיה זו הוצגה כבעלת קושי EXSPACE שנים לפני שהיא הוצגה בכלל ככריעה (Mayr, 1981).