| Property |
Value |
| dbo:abstract
|
- En informatique théorique, et notamment en théorie de la complexité, les machines de Turing alternantes sont une généralisation des machines de Turing non déterministes. Leur mode d'acceptation généralise les conditions d'acceptation utilisées dans les classes de complexité NP et co-NP. Le concept de machine de Turing alternante a été formulé par Ashok K. Chandra et Larry Stockmeyer et indépendamment par Dexter Kozen en 1976, avec un article publié en commun en 1981. Chandra et Stockmeyer les utilisent pour démontrer des bornes inférieures en temps exponentiel pour des jeux à deux joueurs. Les machines alternantes donnent une autre interprétation de la hiérarchie polynomiale. (fr)
- En informatique théorique, et notamment en théorie de la complexité, les machines de Turing alternantes sont une généralisation des machines de Turing non déterministes. Leur mode d'acceptation généralise les conditions d'acceptation utilisées dans les classes de complexité NP et co-NP. Le concept de machine de Turing alternante a été formulé par Ashok K. Chandra et Larry Stockmeyer et indépendamment par Dexter Kozen en 1976, avec un article publié en commun en 1981. Chandra et Stockmeyer les utilisent pour démontrer des bornes inférieures en temps exponentiel pour des jeux à deux joueurs. Les machines alternantes donnent une autre interprétation de la hiérarchie polynomiale. (fr)
|
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 14420 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| prop-fr:année
|
- 1993 (xsd:integer)
- 2006 (xsd:integer)
- 2012 (xsd:integer)
|
| prop-fr:auteur
| |
| prop-fr:isbn
|
- 0 (xsd:integer)
- 978 (xsd:integer)
|
| prop-fr:langue
| |
| prop-fr:lieu
|
- Reading (fr)
- Reading (fr)
|
| prop-fr:lireEnLigne
| |
| prop-fr:numéroD'édition
| |
| prop-fr:pagesTotales
|
- 400 (xsd:integer)
- 432 (xsd:integer)
- 523 (xsd:integer)
|
| prop-fr:passage
|
- Section 10.3: Alternation, (fr)
- Section 16.2: Alternation, (fr)
- Section 10.3: Alternation, (fr)
- Section 16.2: Alternation, (fr)
|
| prop-fr:titre
|
- Computational Complexity (fr)
- Introduction to the Theory of Computation (fr)
- Automata Theory and its Applications (fr)
- Computational Complexity (fr)
- Introduction to the Theory of Computation (fr)
- Automata Theory and its Applications (fr)
|
| prop-fr:wikiPageUsesTemplate
| |
| prop-fr:éditeur
|
- Springer Science & Business Media (fr)
- Addison Wesley (fr)
- PWS Publishing (fr)
- Springer Science & Business Media (fr)
- Addison Wesley (fr)
- PWS Publishing (fr)
|
| dct:subject
| |
| rdfs:comment
|
- En informatique théorique, et notamment en théorie de la complexité, les machines de Turing alternantes sont une généralisation des machines de Turing non déterministes. Leur mode d'acceptation généralise les conditions d'acceptation utilisées dans les classes de complexité NP et co-NP. Le concept de machine de Turing alternante a été formulé par Ashok K. Chandra et Larry Stockmeyer et indépendamment par Dexter Kozen en 1976, avec un article publié en commun en 1981. Chandra et Stockmeyer les utilisent pour démontrer des bornes inférieures en temps exponentiel pour des jeux à deux joueurs. Les machines alternantes donnent une autre interprétation de la hiérarchie polynomiale. (fr)
- En informatique théorique, et notamment en théorie de la complexité, les machines de Turing alternantes sont une généralisation des machines de Turing non déterministes. Leur mode d'acceptation généralise les conditions d'acceptation utilisées dans les classes de complexité NP et co-NP. Le concept de machine de Turing alternante a été formulé par Ashok K. Chandra et Larry Stockmeyer et indépendamment par Dexter Kozen en 1976, avec un article publié en commun en 1981. Chandra et Stockmeyer les utilisent pour démontrer des bornes inférieures en temps exponentiel pour des jeux à deux joueurs. Les machines alternantes donnent une autre interprétation de la hiérarchie polynomiale. (fr)
|
| rdfs:label
|
- Alternating Turing machine (en)
- Alternierende Turingmaschine (de)
- Machine de Turing alternante (fr)
- Màquina de Turing alternant (ca)
- Máquina de Turing alternante (es)
- 交替式图灵机 (zh)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:knownFor
of | |
| is dbo:wikiPageWikiLink
of | |
| is prop-fr:renomméPour
of | |
| is oa:hasTarget
of | |
| is foaf:primaryTopic
of | |
