A grammatical characterization of exponential-time languages
William C. Rounds · 1975
We show that the languages generated by a constrained form of Chomsky's transformational grammars characterize the languages recognized by Turing machines in deterministic exponential (2cn) time. The constraints on the transformational grammars are satisfied by many, though not all, known grammars in linguistic practice. We also give a simple algebraic characterization of the same class of languages and use it for the linguistic characterization.