This HTML5 document contains 117 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dbpedia-dehttp://de.dbpedia.org/resource/
dctermshttp://purl.org/dc/terms/
yago-reshttp://yago-knowledge.org/resource/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
n15https://global.dbpedia.org/id/
yagohttp://dbpedia.org/class/yago/
dbpedia-ruhttp://ru.dbpedia.org/resource/
dbthttp://dbpedia.org/resource/Template:
dbpedia-ukhttp://uk.dbpedia.org/resource/
rdfshttp://www.w3.org/2000/01/rdf-schema#
freebasehttp://rdf.freebase.com/ns/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
dbpedia-frhttp://fr.dbpedia.org/resource/
wikipedia-enhttp://en.wikipedia.org/wiki/
dbchttp://dbpedia.org/resource/Category:
dbphttp://dbpedia.org/property/
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
goldhttp://purl.org/linguistics/gold/
wikidatahttp://www.wikidata.org/entity/
dbrhttp://dbpedia.org/resource/

Statements

Subject Item
dbr:Clique-width
dbo:wikiPageWikiLink
dbr:Courcelle's_theorem
Subject Item
dbr:Logic_of_graphs
dbo:wikiPageWikiLink
dbr:Courcelle's_theorem
Subject Item
dbr:Halin_graph
dbo:wikiPageWikiLink
dbr:Courcelle's_theorem
Subject Item
dbr:Tree_automaton
dbo:wikiPageWikiLink
dbr:Courcelle's_theorem
Subject Item
dbr:Treewidth
dbo:wikiPageWikiLink
dbr:Courcelle's_theorem
Subject Item
dbr:K-outerplanar_graph
dbo:wikiPageWikiLink
dbr:Courcelle's_theorem
Subject Item
dbr:Trémaux_tree
dbo:wikiPageWikiLink
dbr:Courcelle's_theorem
Subject Item
dbr:Courcelle's_theorem
rdf:type
yago:Rule105846932 yago:WikicatGraphAlgorithms yago:Abstraction100002137 yago:YagoPermanentlyLocatedEntity yago:Procedure101023820 yago:Event100029378 yago:Activity100407535 yago:PsychologicalFeature100023100 yago:Act100030358 yago:Algorithm105847438
rdfs:label
Теорема Курселя Теорема Курселя Théorème de Courcelle Courcelle's theorem Courcelles Theorem
rdfs:comment
Теоре́ма Курселя — твердження про те, що будь-яку властивість графа, що визначається в , можна встановити за лінійний час на графах з обмеженою деревною шириною. Результат уперше довів 1990 року і незалежно перевідкрили Борі, Паркер і Товей. Результат вважають прототипом алгоритмічних метатеорем. En algorithmique et en théorie de la complexité, le théorème de Courcelle est le suivant : Théorème de Courcelle — Toute propriété de la logique monadique du second ordre est décidable en temps linéaire dans la classe des graphes avec une largeur arborescente bornée. Теорема Курселя — утверждение о том, что любое свойство графа, определяемое в , может быть установлено за линейное время на графах с ограниченной древесной шириной. Результат впервые доказан в 1990 году и независимо переоткрыт Бори, Паркером и Товейем.Результат считается прототипом алгоритмических метатеорем. In the study of graph algorithms, Courcelle's theorem is the statement that every graph property definable in the monadic second-order logic of graphs can be decided in linear time on graphs of bounded treewidth. The result was first proved by Bruno Courcelle in 1990 and independently rediscovered by .It is considered the archetype of algorithmic meta-theorems.
dcterms:subject
dbc:Graph_minor_theory dbc:Metatheorems dbc:Graph_algorithms
dbo:wikiPageID
35810608
dbo:wikiPageRevisionID
1102259762
dbo:wikiPageWikiLink
dbr:Manifold dbr:Automata_theory dbr:L_(complexity) dbr:Halin_graph dbr:Mikołaj_Bojańczyk dbr:Simplicial_complex dbr:Dual_graph dbc:Graph_minor_theory dbr:Cut_(graph_theory) dbr:Discrete_Morse_theory dbr:Independent_set_(graph_theory) dbr:Graph_coloring dbr:Satisfiability_problem dbr:Grid_graph dbr:Graph_minor dbr:Decision_problem dbr:Treewidth dbr:Meta-theorem dbr:Graph_labeling dbr:Optimization_problem dbr:Undecidable_problem dbr:Elementary_function dbc:Metatheorems dbr:Modular_arithmetic dbr:Monadic_second-order_logic dbr:Quantum_invariants dbr:Approximation_algorithm dbr:Hamiltonian_cycle dbr:Tree_automaton dbr:Tree_decomposition dbr:Time_complexity dbr:Naming_convention_(programming) dbr:Graph_theory dbr:Graph_property dbr:Space_complexity dbr:Cardinality dbr:Parameterized_complexity dbr:Clique-width dbr:Robertson–Seymour_theorem dbr:Paul_Seymour_(mathematician) dbr:Logic_of_graphs dbr:Linear_time dbr:Database_theory dbr:Crossing_number_(graph_theory) dbr:Binary_tree dbr:Bruno_Courcelle dbr:Equivalence_class dbr:Neil_Robertson_(mathematician) dbr:Equivalence_relation dbr:Deterministic_Turing_machine dbr:Graph_(discrete_mathematics) dbc:Graph_algorithms dbr:P_=_NP dbr:Algorithm dbr:Knowledge_representation_and_reasoning dbr:Model_checking
owl:sameAs
wikidata:Q5178114 n15:4iRZK freebase:m.0jt8bld yago-res:Courcelle's_theorem dbpedia-de:Courcelles_Theorem dbpedia-ru:Теорема_Курселя dbpedia-fr:Théorème_de_Courcelle dbpedia-uk:Теорема_Курселя
dbp:wikiPageUsesTemplate
dbt:Harvtxt dbt:Reflist
dbo:abstract
En algorithmique et en théorie de la complexité, le théorème de Courcelle est le suivant : Théorème de Courcelle — Toute propriété de la logique monadique du second ordre est décidable en temps linéaire dans la classe des graphes avec une largeur arborescente bornée. C'est un métathéorème, dans le sens où il concerne une classe de problèmes algorithmiques. Le théorème est dû à Bruno Courcelle. Dans le contexte de ce théorème, un graphe est donné par un ensemble de sommets et une relation d'adjacence , et la restriction à la logique monadique signifie que la propriété étudiée peut contenir des quantificateurs sur des ensembles de sommets (quantificateurs du second ordre sur des prédicats monadiques), mais pas de quantificateurs sur des ensembles d'arcs (ces quantificateurs du second ordre porteraient sur des prédicats binaires). In the study of graph algorithms, Courcelle's theorem is the statement that every graph property definable in the monadic second-order logic of graphs can be decided in linear time on graphs of bounded treewidth. The result was first proved by Bruno Courcelle in 1990 and independently rediscovered by .It is considered the archetype of algorithmic meta-theorems. Теоре́ма Курселя — твердження про те, що будь-яку властивість графа, що визначається в , можна встановити за лінійний час на графах з обмеженою деревною шириною. Результат уперше довів 1990 року і незалежно перевідкрили Борі, Паркер і Товей. Результат вважають прототипом алгоритмічних метатеорем. Теорема Курселя — утверждение о том, что любое свойство графа, определяемое в , может быть установлено за линейное время на графах с ограниченной древесной шириной. Результат впервые доказан в 1990 году и независимо переоткрыт Бори, Паркером и Товейем.Результат считается прототипом алгоритмических метатеорем.
gold:hypernym
dbr:Statement
prov:wasDerivedFrom
wikipedia-en:Courcelle's_theorem?oldid=1102259762&ns=0
dbo:wikiPageLength
24719
foaf:isPrimaryTopicOf
wikipedia-en:Courcelle's_theorem
Subject Item
dbr:Cograph
dbo:wikiPageWikiLink
dbr:Courcelle's_theorem
Subject Item
dbr:Distance-hereditary_graph
dbo:wikiPageWikiLink
dbr:Courcelle's_theorem
Subject Item
dbr:Büchi-Elgot-Trakhtenbrot_theorem
dbo:wikiPageWikiLink
dbr:Courcelle's_theorem
Subject Item
dbr:Bruno_Courcelle
dbo:wikiPageWikiLink
dbr:Courcelle's_theorem
dbp:knownFor
dbr:Courcelle's_theorem
dbo:knownFor
dbr:Courcelle's_theorem
Subject Item
dbr:Second-order_logic
dbo:wikiPageWikiLink
dbr:Courcelle's_theorem
Subject Item
dbr:Monadic_second-order_logic
dbo:wikiPageWikiLink
dbr:Courcelle's_theorem
Subject Item
dbr:List_of_theorems
dbo:wikiPageWikiLink
dbr:Courcelle's_theorem
Subject Item
dbr:Monochromatic_triangle
dbo:wikiPageWikiLink
dbr:Courcelle's_theorem
Subject Item
dbr:S2S_(mathematics)
dbo:wikiPageWikiLink
dbr:Courcelle's_theorem
Subject Item
wikipedia-en:Courcelle's_theorem
foaf:primaryTopic
dbr:Courcelle's_theorem