The emptiness problem for indexed language is exponential‐time complete
Shinichi Tanaka, Takumi Kasai · Systems and Computers in Japan · 1986
Abstract The class of indexed languages properly includes the class of context‐free languages and is properly included in the class of context‐dependent languages [1]. The emptiness problem (the problem of determining whether or not the given language is empty) is polynomial‐time complete for the class of context‐free languages and is undecidable for the class of context‐dependent languages. The recognition problem (the problem, given a language L and word w, of determining whether or not w belongs to L) is polynomial‐time complete for the class of context‐free languages and is polynomialspace complete for the class of contextdependent languages. This paper shows that both the emptiness and recognition problems are exponential‐time complete for the class of indexed languages. It is known in the pebble game [2] that the problem of determining whether or not the first player has the winning strategy is exponential‐time complete. This paper reduces the problem to the emptiness problem for the class of indexed languages in the logarithmic space, indicating the exponential‐time difficulty of the emptiness problem for the indexed language. Since Aho has shown that the problem can be answered in exponential time, the exponential‐time completeness is shown. The exponential‐time difficulty is also directly indicated from the fact that the emptiness problem is exponential‐time complete. Consequently, the recognition problem is also exponential‐time complete.