For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Some EXPTIME Complete Problems on Context-Free Languages
Takumi KASAI Shigeki IWATA
IEICE TRANSACTIONS on Information and Systems
Publication Date: 1993/03/25
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Algorithm and Computational Complexity
computational complexity, EXPTIME complete, context-free language, pebble game problem,
Full Text: PDF(564.3KB)>>
Some problems in formal language theory are considered and are shown to be deterministic exponential time complete. They include the problems for a given context-free grammar G, a nondeterministic finite automaton M, a deterministic pushdown automaton MD, of determining whether L(G)L(M), and whether L(MD)L(M). Polynomial time reductions are presented from the pebble game problem, known to be deterministic exponential time complete, to each of these problems.