Some EXPTIME Complete Problems on Context-Free Languages

スポンサーリンク

概要

• 論文の詳細を見る

• 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 M_D, of determining whether L(G)⊂L(M), and whether L(M_D)⊂L(M). Polynomial time reductions are presented from the pebble game problem, known to be deterministic exponential time complete, to each of these problems.

• 社団法人電子情報通信学会の論文
• 1993-03-25

著者

• Kasai Takumi

  Faculty Of Electro-communications University Of Electro-communications

• Kasai T

  Univ. Electro‐communications Chofu‐shi Jpn

• Iwata Shigeki

  Information Science Laboratory Tokai University

関連論文

• Inherent Ambiguity of Languages Generated by Spine Grammars(Automata and Formal Language Theory)
• Some Problems in Formal Language Theory Known as Decidable are Proved EXPTIME Complete
• Exhaustive Computation to Derive the Lower Bound for Sorting 13 Items
• Some EXPTIME Complete Problems on Context-Free Languages

スポンサーリンク