| Property |
Value |
| 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). (fr)
- 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). (fr)
|
| dbo:namedAfter
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 4164 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| prop-fr:nom
|
- Théorème de Courcelle (fr)
- Théorème de Courcelle (fr)
|
| prop-fr:wikiPageUsesTemplate
| |
| prop-fr:énoncé
|
- 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. (fr)
- 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. (fr)
|
| dct:subject
| |
| rdfs:comment
|
- 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. (fr)
- 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. (fr)
|
| rdfs:label
|
- Théorème de Courcelle (fr)
- Courcelles Theorem (de)
- Théorème de Courcelle (fr)
- Courcelles Theorem (de)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageWikiLink
of | |
| is oa:hasTarget
of | |
| is foaf:primaryTopic
of | |
