2013/4/8/ (月) 23:44時点におけるja>Addbotによる版
計算複雑性理論において、複雑性クラス LOGCFL とは、文脈自由言語に還元可能な対数領域で解ける決定問題の集合である。"logarithmic space context-free language" の略。
NLとAC1の間に位置する。すなわち、NL を包含し、AC1 に包含される。LOGCFL完全な問題としては、具体的な問題を非周期的ハイパーグラフで表せる問題が多く含まれる。例えば次のような問題である。
外部リンク