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 lenguaje libre de contexto. Esta clase se sitúa entre NL y AC1, 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.

rdfs:comment
  • 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 lenguaje libre de contexto. Esta clase se sitúa entre NL y AC1, 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)
foaf:isPrimaryTopicOf
rdfs:label
  • LOGCFL (es)
Is foaf:primaryTopic of
dcterms:subject
prov:wasDerivedFrom
dbpedia-owl:wikiPageExternalLink
dbpedia-owl:wikiPageID
  • 3955541 (xsd:integer)
dbpedia-owl:wikiPageLength
  • 807 (xsd:integer)
dbpedia-owl:wikiPageOutDegree
  • 13 (xsd:integer)
dbpedia-owl:wikiPageRevisionID
  • 64690382 (xsd:integer)
dbpedia-owl:wikiPageWikiLink [13 values]