About: Descriptive complexity theory

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: Descriptive complexity theory Goto Sponge NotDistinct Permalink

An Entity of Type : owl:Thing, within Data Space : prod-dbpedia.inria.fr associated with source document(s)

Attributes	Values
rdfs:label	Complexité descriptive (fr) Descriptive complexity theory (en) Deskriptive Komplexitätstheorie (de)
rdfs:comment	En informatique théorique, la complexité descriptive est une branche de la théorie de la complexité et de la théorie des modèles, qui caractérise les classes de complexité en termes de logique qui permet de décrire les problèmes. La complexité descriptive donne un nouveau point de vue car on définit des classes de complexité sans faire appel à une notion de machines comme les machines de Turing. Par exemple la classe NP correspond à l'ensemble des problèmes exprimables en logique du second ordre existentielle : c'est le théorème de Fagin. (fr)
sameAs	Descriptive complexity theory Descriptive complexity theory Descriptive complexity theory Descriptive complexity theory Descriptive complexity theory Descriptive complexity theory
Wikipage page ID	7542341 (xsd:integer)
Wikipage revision ID	183943370 (xsd:integer)
dbo:wikiPageWikiLink	category-fr:Théorie_des_modèles AC0 Bisimulation First-order logic category-fr:Théorie_de_la_complexité_des_algorithmes dbpedia-fr:Classe_de_complexité dbpedia-fr:Coloration_de_graphe ELEMENTARY EXPTIME Polynomial hierarchy Theoretical computer science dbpedia-fr:Logique_d'ordre_supérieur dbpedia-fr:Logique_mathématique Turing machine Modal μ-calculus NL (complexity) NP (complexity) Neil Immerman dbpedia-fr:PSPACE dbpedia-fr:P_(complexité) dbpedia-fr:Problème_de_décision Ronald Fagin dbpedia-fr:Récursivement_énumérable dbpedia-fr:Serge_Abiteboul dbpedia-fr:Théorie_de_la_complexité_(informatique_théorique) dbpedia-fr:Théorie_des_modèles dbpedia-fr:Théorème_de_Fagin
Link from a Wikipage to an external page	http://people.cs.umass.edu/~immerman/book/descriptiveComplexity.html https://researcher.watson.ibm.com/researcher/files/us-fagin/genspec.pdf http://people.cs.umass.edu/~immerman/descriptive_complexity.html http://people.cs.umass.edu/~immerman/pub/capture.pdf http://citeseerx.ist.psu.edu/viewdoc/download%3Fdoi=10.1.1.698.6420&rep=rep1&type=pdf
page length (characters) of wiki page	9148 (xsd:nonNegativeInteger)
dct:subject	category-fr:Théorie_des_modèles category-fr:Théorie_de_la_complexité_des_algorithmes
prop-fr:wikiPageUsesTemplate	dbpedia-fr:Modèle:, dbpedia-fr:Modèle:Article dbpedia-fr:Modèle:Article_détaillé dbpedia-fr:Modèle:Lien dbpedia-fr:Modèle:Ouvrage dbpedia-fr:Modèle:Portail dbpedia-fr:Modèle:Références dbpedia-fr:Modèle:Section_vide_ou_incomplète
prov:wasDerivedFrom	wikipedia-fr:Complexité_descriptive?oldid=183943370&ns=0
foaf:depiction
prop-fr:année	1974 (xsd:integer) 1983 (xsd:integer) 1991 (xsd:integer) 1999 (xsd:integer) 2017 (xsd:integer)
prop-fr:consultéLe	2019-11-07 (xsd:date)
prop-fr:doi	10 (xsd:double)
prop-fr:fr	Victor Vianu (fr)
prop-fr:id	Fagin 1974 (fr)
prop-fr:isbn	0 (xsd:integer) 978 (xsd:integer)
prop-fr:journal	STOC '91 Proceedings of the twenty-third annual ACM symposium on Theory of Computing (fr) STOC '83 Proceedings of the fifteenth annual ACM symposium on Theory of computing (fr)
prop-fr:langue	en (fr)
prop-fr:lienAuteur	Neil Immerman (fr) Serge Abiteboul (fr)
prop-fr:lieu	New York (fr)
prop-fr:lireEnLigne	https://researcher.watson.ibm.com/researcher/files/us-fagin/genspec.pdf http://people.cs.umass.edu/~immerman/pub/capture.pdf http://citeseerx.ist.psu.edu/viewdoc/download%3Fdoi=10.1.1.698.6420&rep=rep1&type=pdf
prop-fr:nom	Ronald Fagin Immerman (fr) Abiteboul (fr) Grohe (fr) Vianu (fr)
prop-fr:pages	43 (xsd:integer)
prop-fr:pagesTotales	554 (xsd:integer)
prop-fr:passage	40 (xsd:integer) 209 (xsd:integer) 347 (xsd:integer)
prop-fr:prénom	Victor (fr) Martin (fr) Serge (fr) Neil (fr)
prop-fr:présentationEnLigne	http://people.cs.umass.edu/~immerman/book/descriptiveComplexity.html
prop-fr:périodique	Proc. SIAM-AMS Sympos. Appl. Math. (fr)
prop-fr:texte	Vianu (fr)
prop-fr:titre	Descriptive Complexity, Canonisation, and Definable Graph Structure Theory (fr) Descriptive Complexity (fr) Generic Computation and Its Complexity (fr) Languages Which Capture Complexity Classes (fr) Generalized First-Order Spectra and Polynomial-Time Recognizable Sets (fr)

Faceted Search & Find service v1.16.111 as of Oct 19 2022

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3234 as of May 18 2022, on Linux (x86_64-ubuntu_bionic-linux-gnu), Single-Server Edition (39 GB total memory, 14 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software