Some Problems in Formal Language Theory Known as Decidable are Proved EXPTIME Complete
Takumi Kasai, Shigeki Iwata · Kyoto University Research Information Repository (Kyoto University) · 1992
Some problems in formal language theory are considered and shown deterministic exponential time complete.They include the problems for a given context-free language $L$ , a regular set $R$ , a deterministic context-free language $L_{D}$ , to determine whether $L\subset R$ , and to determine whether $L_{D}\subset R$ .