Some EXPTIME Complete Problems on Context-Free Languages

Takumi KASAI  Shigeki IWATA  

IEICE TRANSACTIONS on Information and Systems   Vol.E76-D   No.3   pp.329-335
Publication Date: 1993/03/25
Online ISSN: 
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)>>
Buy this Article

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.