On the Exponentiation of Languages

摘要

We characterize the exponentiation of languages by other language operations: In the presence of some "weak" operations, exponentiation is exactly as powerful as complement and ε-free morphism. This characterization implies, besides others, that a semi-AFL is closed under complement iff it is closed under exponentiation. As an application we characterize the exponentiation closure of the context-free languages. Furthermore, P is closed under exponentiation iff P = NP , and NP is closed under exponentiation iff NP = co-NP.