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:
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - LOGCFL (de)
- LOGCFL (es)
- LOGCFL (fr)
- LOGCFL (en)
- LOGCFL (ja)
|
| 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)
|
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| has 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)
|
| gold:hypernym
| |
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
| is foaf:primaryTopic
of | |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)