LOGCFL (original) (raw)
In der Komplexitätstheorie bezeichnet LOGCFL die Komplexitätsklasse der Entscheidungsprobleme, die mit logarithmischem Speicheraufwand auf eine kontextfreie Sprache (englisch context-free language) reduziert werden können.
| Property | Value |
|---|---|
| dbo:abstract | In der Komplexitätstheorie bezeichnet LOGCFL die Komplexitätsklasse der Entscheidungsprobleme, die mit logarithmischem Speicheraufwand auf eine kontextfreie Sprache (englisch context-free language) reduziert werden können. (de) In computational complexity theory, LOGCFL is the complexity class that contains all decision problems that can be reduced in logarithmic space to a context-free language. This class is situated between NL and AC1, in the sense that it contains the former and is contained in the latter. Problems that are complete for LOGCFL include many problems whose can be characterized by acyclic hypergraphs: * evaluating acyclic Boolean conjunctive queries * checking the existence of a homomorphism between two acyclic relational structures * checking the existence of solutions of acyclic constraint satisfaction problems (en) En complejidad computacional, LOGCFL es la clase de complejidad que contiene todos los problemas de decisión que pueden ser reducidos en espacio logarítmico a un . Esta clase se sitúa entre NL y , en el sentido que contiene la primera y es contenida por la segunda. Los problemas completos para LOGCFL (en el mismo sentido que la clase NP-completo con respecto a NP) incluye muchos problemas cuyas instancias pueden ser caracterizadas mediante hipergrafos acíclicos. (es) En théorie de la complexité, LOGCFL (pour Logarithmically Reducible to context-free language en anglais) désigne la classe des problèmes réductibles en espace logarithmique à un langage hors contexte. On a NL ⊆ LOGCFL ⊆ AC1. (fr) 計算複雑性理論において、複雑性クラス LOGCFL とは、文脈自由言語に還元可能な対数領域で解ける決定問題の集合である。"logarithmic space context-free language" の略。 NLとの間に位置する。すなわち、NL を包含し、AC1 に包含される。LOGCFL完全な問題としては、具体的な問題を非周期的ハイパーグラフで表せる問題が多く含まれる。例えば次のような問題である。 * 非周期的な論理積型クエリの評価 * 2つの非周期的関係構造の間に準同型写像が存在するかのチェック * 非周期的制約充足問題に解が存在するかのチェック (ja) |
| dbo:wikiPageID | 4734121 (xsd:integer) |
| dbo:wikiPageLength | 976 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 914120701 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:List_of_complexity_classes dbr:Homomorphism dbr:Decision_problem dbr:NL_(complexity) dbr:Constraint_satisfaction_problem dbr:Context-free_language dbr:Complete_(complexity) dbr:Complexity_class dbr:Computational_complexity_theory dbc:Complexity_classes dbr:Hypergraph dbr:AC_(complexity) dbr:Directed_acyclic_graph dbr:Boolean_conjunctive_query dbr:Relational_structure dbr:Logarithmic_space dbr:Problem_instance |
| dbp:wikiPageUsesTemplate | dbt:CZoo dbt:Comp-sci-theory-stub |
| dct:subject | dbc:Complexity_classes |
| gold:hypernym | dbr:Class |
| rdf:type | yago:WikicatComplexityClasses yago:Abstraction100002137 yago:Class107997703 yago:Collection107951464 yago:Group100031264 |
| rdfs:comment | In der Komplexitätstheorie bezeichnet LOGCFL die Komplexitätsklasse der Entscheidungsprobleme, die mit logarithmischem Speicheraufwand auf eine kontextfreie Sprache (englisch context-free language) reduziert werden können. (de) En complejidad computacional, LOGCFL es la clase de complejidad que contiene todos los problemas de decisión que pueden ser reducidos en espacio logarítmico a un . Esta clase se sitúa entre NL y , en el sentido que contiene la primera y es contenida por la segunda. Los problemas completos para LOGCFL (en el mismo sentido que la clase NP-completo con respecto a NP) incluye muchos problemas cuyas instancias pueden ser caracterizadas mediante hipergrafos acíclicos. (es) En théorie de la complexité, LOGCFL (pour Logarithmically Reducible to context-free language en anglais) désigne la classe des problèmes réductibles en espace logarithmique à un langage hors contexte. On a NL ⊆ LOGCFL ⊆ AC1. (fr) 計算複雑性理論において、複雑性クラス LOGCFL とは、文脈自由言語に還元可能な対数領域で解ける決定問題の集合である。"logarithmic space context-free language" の略。 NLとの間に位置する。すなわち、NL を包含し、AC1 に包含される。LOGCFL完全な問題としては、具体的な問題を非周期的ハイパーグラフで表せる問題が多く含まれる。例えば次のような問題である。 * 非周期的な論理積型クエリの評価 * 2つの非周期的関係構造の間に準同型写像が存在するかのチェック * 非周期的制約充足問題に解が存在するかのチェック (ja) In computational complexity theory, LOGCFL is the complexity class that contains all decision problems that can be reduced in logarithmic space to a context-free language. This class is situated between NL and AC1, in the sense that it contains the former and is contained in the latter. Problems that are complete for LOGCFL include many problems whose can be characterized by acyclic hypergraphs: (en) |
| rdfs:label | LOGCFL (de) LOGCFL (es) LOGCFL (fr) LOGCFL (en) LOGCFL (ja) |
| owl:sameAs | freebase:LOGCFL yago-res:LOGCFL wikidata:LOGCFL dbpedia-de:LOGCFL dbpedia-es:LOGCFL dbpedia-fr:LOGCFL dbpedia-ja:LOGCFL https://global.dbpedia.org/id/49jPJ |
| prov:wasDerivedFrom | wikipedia-en:LOGCFL?oldid=914120701&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:LOGCFL |
| is dbo:wikiPageWikiLink of | dbr:List_of_complexity_classes dbr:Integer_circuit dbr:Conjunctive_query dbr:Circuits_over_sets_of_natural_numbers dbr:Immerman–Szelepcsényi_theorem |
| is foaf:primaryTopic of | wikipedia-en:LOGCFL |