{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,21]],"date-time":"2023-10-21T19:41:53Z","timestamp":1697917313535},"reference-count":4,"publisher":"Wiley","issue":"9","license":[{"start":{"date-parts":[[2007,3,21]],"date-time":"2007-03-21T00:00:00Z","timestamp":1174435200000},"content-version":"vor","delay-in-days":7749,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Systems &amp; Computers in Japan"],"published-print":{"date-parts":[[1986,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The class of indexed languages properly includes the class of context\u2010free languages and is properly included in the class of context\u2010dependent languages [1]. The emptiness problem (the problem of determining whether or not the given language is empty) is polynomial\u2010time complete for the class of context\u2010free languages and is undecidable for the class of context\u2010dependent languages. The recognition problem (the problem, given a language <jats:italic>L<\/jats:italic> and word <jats:italic>w<\/jats:italic>, of determining whether or not <jats:italic>w<\/jats:italic> belongs to <jats:italic>L<\/jats:italic>) is polynomial\u2010time complete for the class of context\u2010free languages and is polynomialspace complete for the class of contextdependent languages. This paper shows that both the emptiness and recognition problems are exponential\u2010time 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\u2010time complete. This paper reduces the problem to the emptiness problem for the class of indexed languages in the logarithmic space, indicating the exponential\u2010time difficulty of the emptiness problem for the indexed language. Since Aho has shown that the problem can be answered in exponential time, the exponential\u2010time completeness is shown. The exponential\u2010time difficulty is also directly indicated from the fact that the emptiness problem is exponential\u2010time complete. Consequently, the recognition problem is also exponential\u2010time complete.<\/jats:p>","DOI":"10.1002\/scj.4690170904","type":"journal-article","created":{"date-parts":[[2007,7,7]],"date-time":"2007-07-07T12:32:20Z","timestamp":1183811540000},"page":"29-37","source":"Crossref","is-referenced-by-count":3,"title":["The emptiness problem for indexed language is exponential\u2010time complete"],"prefix":"10.1002","volume":"17","author":[{"given":"Shinichi","family":"Tanaka","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Takumi","family":"Kasai","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2007,3,21]]},"reference":[{"key":"e_1_2_1_2_2","first-page":"4","article-title":"Indexed grammars","volume":"15","author":"Aho A. V.","year":"1986","journal-title":"J. ACM"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1137\/0208046"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/62.322433"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(84)90023-9"}],"container-title":["Systems and Computers in Japan"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fscj.4690170904","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/scj.4690170904","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,20]],"date-time":"2023-10-20T17:16:25Z","timestamp":1697822185000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/scj.4690170904"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986,1]]},"references-count":4,"journal-issue":{"issue":"9","published-print":{"date-parts":[[1986,1]]}},"alternative-id":["10.1002\/scj.4690170904"],"URL":"https:\/\/doi.org\/10.1002\/scj.4690170904","archive":["Portico"],"relation":{},"ISSN":["0882-1666","1520-684X"],"issn-type":[{"value":"0882-1666","type":"print"},{"value":"1520-684X","type":"electronic"}],"subject":[],"published":{"date-parts":[[1986,1]]}}}