| Property |
Value |
| dbo:abstract
|
- En informatique théorique, et notamment en théorie des automates, l'algorithme appelé la construction par sous-ensembles, en anglais « powerset construction » ou « subset construction », est la méthode usuelle pour convertir un automate fini non déterministe (abrégé en « AFN ») en un automate fini déterministe (abrégé en « AFD ») équivalent, c'est-à-dire qui reconnaît le même langage rationnel. L'existence même d'une conversion, et l'existence d'un algorithme pour la réaliser, est remarquable et utile. Elle est remarquable parce qu'il existe peu de modèles de machines pour lesquels les versions déterministe et non déterministe ont la même puissance de reconnaissance : ainsi, les automates à pile déterministes sont moins puissants que les automates à pile généraux. Elle est utile dans la pratique parce que la reconnaissance par un automate déterministe est bien plus facile à mettre en œuvre que la reconnaissance par automate non déterministe. Toutefois, la construction par sous-ensembles peut produire un automate dont la taille, mesurée en nombre d'états, est exponentielle par rapport à la taille de l'automate de départ. La construction par sous-ensembles a été publiée pour la première fois par Michael O. Rabin et Dana S. Scott dans un article fondateur paru en 1959. Ils ont obtenu le prix Turing pour leurs travaux autour du non-déterminisme en 1976. (fr)
- En informatique théorique, et notamment en théorie des automates, l'algorithme appelé la construction par sous-ensembles, en anglais « powerset construction » ou « subset construction », est la méthode usuelle pour convertir un automate fini non déterministe (abrégé en « AFN ») en un automate fini déterministe (abrégé en « AFD ») équivalent, c'est-à-dire qui reconnaît le même langage rationnel. L'existence même d'une conversion, et l'existence d'un algorithme pour la réaliser, est remarquable et utile. Elle est remarquable parce qu'il existe peu de modèles de machines pour lesquels les versions déterministe et non déterministe ont la même puissance de reconnaissance : ainsi, les automates à pile déterministes sont moins puissants que les automates à pile généraux. Elle est utile dans la pratique parce que la reconnaissance par un automate déterministe est bien plus facile à mettre en œuvre que la reconnaissance par automate non déterministe. Toutefois, la construction par sous-ensembles peut produire un automate dont la taille, mesurée en nombre d'états, est exponentielle par rapport à la taille de l'automate de départ. La construction par sous-ensembles a été publiée pour la première fois par Michael O. Rabin et Dana S. Scott dans un article fondateur paru en 1959. Ils ont obtenu le prix Turing pour leurs travaux autour du non-déterminisme en 1976. (fr)
|
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 11848 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| prop-fr:année
|
- 1959 (xsd:integer)
- 1979 (xsd:integer)
- 1997 (xsd:integer)
- 2004 (xsd:integer)
- 2006 (xsd:integer)
|
| prop-fr:auteur
|
- James A. Anderson (fr)
- Thomas J. Head (fr)
- Klaus Schneider (fr)
- James A. Anderson (fr)
- Thomas J. Head (fr)
- Klaus Schneider (fr)
|
| prop-fr:doi
| |
| prop-fr:isbn
|
- 0 (xsd:integer)
- 978 (xsd:integer)
|
| prop-fr:lieu
|
- Reading Massachusetts (fr)
- Reading Massachusetts (fr)
|
| prop-fr:lireEnLigne
| |
| prop-fr:nom
|
- Scott (fr)
- Rabin (fr)
- Hopcroft (fr)
- Ullman (fr)
- Sipser (fr)
- Scott (fr)
- Rabin (fr)
- Hopcroft (fr)
- Ullman (fr)
- Sipser (fr)
|
| prop-fr:numéro
| |
| prop-fr:pages
| |
| prop-fr:pagesTotales
|
- 264 (xsd:integer)
- 396 (xsd:integer)
- 602 (xsd:integer)
|
| prop-fr:passage
|
- 43 (xsd:integer)
- 210 (xsd:integer)
- Chapitre 2 (fr)
- p. 55. Section 1.2, Théorème 1.19 (fr)
|
| prop-fr:prénom
|
- Michael (fr)
- Jeffrey D. (fr)
- John E. (fr)
- Dana (fr)
- Michael O. (fr)
- Michael (fr)
- Jeffrey D. (fr)
- John E. (fr)
- Dana (fr)
- Michael O. (fr)
|
| prop-fr:périodique
|
- IBM Journal of Research and Development (fr)
- IBM Journal of Research and Development (fr)
|
| prop-fr:sousTitre
|
- formal methods and algorithms (fr)
- formal methods and algorithms (fr)
|
| prop-fr:titre
|
- Introduction to Automata Theory, Languages, and Computation (fr)
- Finite automata and their decision problems (fr)
- Automata theory with modern applications (fr)
- Introduction to the Theory of Computation (fr)
- Verification of reactive systems (fr)
- Introduction to Automata Theory, Languages, and Computation (fr)
- Finite automata and their decision problems (fr)
- Automata theory with modern applications (fr)
- Introduction to the Theory of Computation (fr)
- Verification of reactive systems (fr)
|
| prop-fr:volume
| |
| prop-fr:wikiPageUsesTemplate
| |
| prop-fr:éditeur
|
- Springer (fr)
- Cambridge University Press (fr)
- Addison-Wesley Publishing (fr)
- Springer (fr)
- Cambridge University Press (fr)
- Addison-Wesley Publishing (fr)
|
| dct:subject
| |
| rdfs:comment
|
- En informatique théorique, et notamment en théorie des automates, l'algorithme appelé la construction par sous-ensembles, en anglais « powerset construction » ou « subset construction », est la méthode usuelle pour convertir un automate fini non déterministe (abrégé en « AFN ») en un automate fini déterministe (abrégé en « AFD ») équivalent, c'est-à-dire qui reconnaît le même langage rationnel. (fr)
- En informatique théorique, et notamment en théorie des automates, l'algorithme appelé la construction par sous-ensembles, en anglais « powerset construction » ou « subset construction », est la méthode usuelle pour convertir un automate fini non déterministe (abrégé en « AFN ») en un automate fini déterministe (abrégé en « AFD ») équivalent, c'est-à-dire qui reconnaît le même langage rationnel. (fr)
|
| rdfs:label
|
- Construcción de conjunto potencia (es)
- Construction par sous-ensembles (fr)
- Conversão AFN AFD (pt)
- Determinizacja automatu skończonego (pl)
- 幂集构造 (zh)
- Construcción de conjunto potencia (es)
- Construction par sous-ensembles (fr)
- Conversão AFN AFD (pt)
- Determinizacja automatu skończonego (pl)
- 幂集构造 (zh)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageWikiLink
of | |
| is oa:hasTarget
of | |
| is foaf:primaryTopic
of | |
