Word problems requiring exponential time(Preliminary Report)
Larry J. Stockmeyer, Albert R. Meyer · 1973
The equivalence problem for Kleene's regular expressions has several effective solutions, all of which are computationally inefficient. In [1], we showed that this inefficiency is an inherent property of the problem by showing that the problem of membership in any arbitrary context-sensitive language was easily reducible to the equivalence problem for regular expressions. We also showed that with a squaring abbreviation ( writing (E)2 for E×E) the equivalence problem for expressions required computing space exponential in the size of the expressions.