葉の言語

リーフ言語は、計算複雑性理論において、機械が入力を「受け入れる」ことの意味を形式化することで複雑性クラスを特徴付ける手法である。 ^[1]

複雑性クラスは、典型的には多項式時間非決定性チューリングマシン（NTM）を用いて定義されます。これらのマシンは複数の計算パスを持ち、それらのパスの結果によって入力の受理または拒否が決定されます。^[1] 伝統的に、NTMは少なくとも1つのパスが入力を受け入れる場合にのみ入力を受け入れ、すべてのパスが拒否する場合にのみ拒否します。対照的に、共非決定性チューリングマシン（co-NTM）は、すべてのパスが入力を受け入れる場合にのみ入力を受け入れ、いずれかのパスが拒否する場合にのみ入力を拒否します。さらに、より複雑な受理の概念も定義できます。

複雑性クラスの特徴を形式化するために、各受理条件に関連付けられた形式言語を調べることができる。これは、順序付き木を仮定し、計算木の葉から受理/拒否文字列を読み取ることを含む。NTMは、葉文字列が言語 $0*1{0, 1}*$ である場合に受理し、葉文字列が言語 $0*$ である場合に拒否する。^[2]

参考文献

^ ab Wagner, Klaus W. (2005). 「Leaf Language Classes」. Margenstern, Maurice (ed.).機械、計算、そして普遍性. コンピュータサイエンス講義ノート. 第3354巻. ベルリン、ハイデルベルク: Springer. pp. 60– 81. doi :10.1007/978-3-540-31834-7_5. ISBN 978-3-540-31834-7。
^ パパディミトリウ, クリストス・H. (1994).計算複雑性. リーディング（マサチューセッツ州）: アディソン・ウェスレー. ISBN 978-0-201-53082-7。

[:0-1] Wagner, Klaus W. (2005). 「Leaf Language Classes」. Margenstern, Maurice (ed.).機械、計算、そして普遍性. コンピュータサイエンス講義ノート. 第3354巻. ベルリン、ハイデルベルク: Springer. pp. 60– 81. doi :10.1007/978-3-540-31834-7_5. ISBN 978-3-540-31834-7。

[2] パパディミトリウ, クリストス・H. (1994).計算複雑性. リーディング（マサチューセッツ州）: アディソン・ウェスレー. ISBN 978-0-201-53082-7。