ブラウザよりも高速アクセス！
11 関係: ハイパーグラフ、制約充足問題、クエリ、複雑性クラス、計算複雑性理論、論理積、L (計算複雑性理論)、NL (計算複雑性理論)、決定問題、準同型、文脈自由言語。
ハイパーグラフ
ハイパーグラフの例: X.
新しい！!: LOGCFLとハイパーグラフ · 続きを見る »
制約充足問題
制約充足問題（せいやくじゅうそくもんだい、Constraint satisfaction problem, CSP）は、複数の制約条件を満たすオブジェクトや状態を見つけるという数学の問題を指す。CSPは特に人工知能やオペレーションズ・リサーチで研究されている。多くのCSPでは、それなりの時間内に解くのにヒューリスティクスと組合せ最適化手法を組み合わせる必要がある。 制約充足問題の具体例.
新しい！!: LOGCFLと制約充足問題 · 続きを見る »
クエリ
リ（query、 、 （クウィァリ））とは、一般に一連の問い合わせの中の個々の質問を意味する。.
新しい！!: LOGCFLとクエリ · 続きを見る »
複雑性クラス
複雑性クラス（ふくざつせいクラス、Complexity class）は、計算複雑性理論において関連する複雑性の問題の集合を指す。典型的な複雑性クラスは以下のように定義される。 例えば、クラスNPは非決定性チューリングマシンで多項式時間で解く事が出来る決定問題の集合である。また、クラスPSPACEはチューリングマシンで多項式領域で解く事が出来る決定問題の集合である。一部の複雑性クラスは函数問題の集合である（例えば'''FP'''）。 数理論理学では表現の必要に応じて多数の複雑性クラスが定義される（記述計算量）。 ブラムの公理を使うと、完全な計算模型を参照しなくとも複雑性クラスを定義できる。.
新しい！!: LOGCFLと複雑性クラス · 続きを見る »
計算複雑性理論
計算複雑性理論（けいさんふくざつせいりろん、computational complexity theory）とは、計算機科学における計算理論の一分野であり、アルゴリズムのスケーラビリティや、特定の計算問題の解法の複雑性（計算問題の困難さ）などを数学的に扱う。計算量理論、計算の複雑さの理論、計算複雑度の理論ともいう。.
新しい！!: LOGCFLと計算複雑性理論 · 続きを見る »
論理積
数理論理学において論理積（ろんりせき、logical conjunction）とは、与えられた複数の命題のいずれもが例外なく真であることを示す論理演算である。合接（ごうせつ）、連言（れんげん、れんごん）とも呼び、ANDとよく表す。 二つの命題 P, Q に対する論理積を P ∧ Q と書き、「P かつ Q」や「P そして Q」などと読む。 ベン図による論理積P \wedge Q の表.
新しい！!: LOGCFLと論理積 · 続きを見る »
L (計算複雑性理論)
計算量理論において、Lとは、決定性チューリングマシンで対数規模の領域（メモリ）を使って解くことができる決定問題の集合である。直観的には対数領域は、入力を参照するポインタを一定数保持するのに使われたり、対数個のブール値フラグを保持するのに使われたりする。 Lと関連する計算量に'''NL'''がある。NLは、非決定性チューリングマシン上で対数領域で決定可能な言語のクラスである。従って、\mathrm \subseteq \mathrm が成り立つ。 また、O(log n) の領域を使用する決定機械は時間 2O(log n).
新しい！!: LOGCFLとL (計算複雑性理論) · 続きを見る »
NL (計算複雑性理論)
NL（えぬえる、Nondeterministic Logarithmic-space）は、計算複雑性理論における決定問題の複雑性クラスの一つである。非決定性チューリングマシンで対数規模の記憶領域を使って解ける問題がこのクラスに属する。 NL は Lを一般化したものである。L は決定性チューリングマシンでの対数領域問題のクラスである。決定性チューリングマシンは非決定性チューリングマシンに含まれるため、L も NL に含まれる。 NLは非決定性領域(NSPACE)の計算資源記法で形式的に定義でき、NL.
新しい！!: LOGCFLとNL (計算複雑性理論) · 続きを見る »
決定問題
決定問題（けっていもんだい、decision problem）とは、各入力に対して受理か拒絶かのうち片方を出力する形式の問題をいう。判定問題とも呼ばれる。形式的には、文字列全体の集合\ ^*、あるいは\ ^*の部分集合から\への写像である。 たとえば、ある命題論理式を充足する真理値割り当てがあるかないか（充足可能性問題）、与えられた自然数が素数か否か（素数判定問題）、といったものがある。これに対し、受理か拒絶かだけでなく真理値割り当てや素因数分解の結果といったものの出力を要求する問題は函数問題（function problem）と呼ばれる。 決定問題は、数学的に定式化しやすく、かつ出力に関わる時間を考慮しなくてよいことから、計算理論でよく使われる。.
新しい！!: LOGCFLと決定問題 · 続きを見る »
準同型
準同型（じゅんどうけい、homomorphic）とは、複数の対象（おもに代数系）に対して、それらの特定の数学的構造に関する類似性を表す概念で、構造を保つ写像である準同型写像（じゅんどうけいしゃぞう、homomorphism) を持つことを意味する。構造がまったく同じであることを表すときは、準同型・準同型写像の代わりに同型（どうけい、isomorphic）および同型写像（どうけいしゃぞう、isomorphism）という術語を用いる。しばしば、準同型写像・同型写像のことを指して単に準同型・同型と呼ぶ。いずれも、「型」の代わりに「形」が用いられることが稀にある。.
新しい！!: LOGCFLと準同型 · 続きを見る »
文脈自由言語
文脈自由言語（ぶんみゃくじゆうげんご）とは、次のような再帰的な生成規則をもつ文脈自由文法によって、与えられた言語の長さ n に対して O(n3) の時間で認識される形式言語。プッシュダウン・オートマトンで受理可能な言語と等価である。.
新しい！!: LOGCFLと文脈自由言語 · 続きを見る »
