| Property |
Value |
| dbo:abstract
|
- En informatique théorique, et plus particulièrement en théorie des automates, la minimisation d'un automate fini déterministe est l'opération qui consiste à transformer un automate fini déterministe donné en un automate fini déterministe ayant le nombre minimal d'états et qui reconnaît le même langage rationnel. La minimisation a une importance pratique évidente par le gain d'espace qu'elle permet. Il existe plusieurs algorithmes pour effectuer cette opération de minimisation ; les plus usuels sont décrits pour la plupart dans les manuels traitant de théorie des automates. Les algorithmes généraux les plus connus - nommés d'après leurs inventeurs - sont l'algorithme de Brzozowski, l'algorithme de Moore, et l'algorithme de Hopcroft. D'autres algorithmes spécifiques existent, par exemple pour la minimisation d'automates reconnaissant des ensembles finis de mots, comme l'algorithme de Revuz et ses variantes. Les algorithmes ont aussi été étendus à des cas plus généraux, comme les automates avec sortie (automate de Moore, automate de Mealy) ou les transducteurs finis. Il n'existe pas de procédé analogue pour la minimisation d'automates plus généraux, comme les automates à pile ou les automates linéairement bornés. Une application importante de la minimisation des automates finis déterministes est le test de l'équivalence de deux automates finis, c'est-à-dire le fait de décider s'ils reconnaissent le même langage. C'est une conséquence de l'unicité de l'automate fini minimal, à un renommage des états près. Pour répondre à la question, il suffit de minimiser les deux automates et de tester si leurs versions minimales sont égales. Étant donné l'importance de la minimisation, cette opération fait partie de la plupart des logiciels de manipulation d'automates. (fr)
- En informatique théorique, et plus particulièrement en théorie des automates, la minimisation d'un automate fini déterministe est l'opération qui consiste à transformer un automate fini déterministe donné en un automate fini déterministe ayant le nombre minimal d'états et qui reconnaît le même langage rationnel. La minimisation a une importance pratique évidente par le gain d'espace qu'elle permet. Il existe plusieurs algorithmes pour effectuer cette opération de minimisation ; les plus usuels sont décrits pour la plupart dans les manuels traitant de théorie des automates. Les algorithmes généraux les plus connus - nommés d'après leurs inventeurs - sont l'algorithme de Brzozowski, l'algorithme de Moore, et l'algorithme de Hopcroft. D'autres algorithmes spécifiques existent, par exemple pour la minimisation d'automates reconnaissant des ensembles finis de mots, comme l'algorithme de Revuz et ses variantes. Les algorithmes ont aussi été étendus à des cas plus généraux, comme les automates avec sortie (automate de Moore, automate de Mealy) ou les transducteurs finis. Il n'existe pas de procédé analogue pour la minimisation d'automates plus généraux, comme les automates à pile ou les automates linéairement bornés. Une application importante de la minimisation des automates finis déterministes est le test de l'équivalence de deux automates finis, c'est-à-dire le fait de décider s'ils reconnaissent le même langage. C'est une conséquence de l'unicité de l'automate fini minimal, à un renommage des états près. Pour répondre à la question, il suffit de minimiser les deux automates et de tester si leurs versions minimales sont égales. Étant donné l'importance de la minimisation, cette opération fait partie de la plupart des logiciels de manipulation d'automates. (fr)
|
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 31726 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| prop-fr:année
|
- 1956 (xsd:integer)
- 1963 (xsd:integer)
- 1970 (xsd:integer)
- 1971 (xsd:integer)
- 1973 (xsd:integer)
- 1974 (xsd:integer)
- 1981 (xsd:integer)
- 1996 (xsd:integer)
- 1999 (xsd:integer)
- 2001 (xsd:integer)
- 2003 (xsd:integer)
- 2010 (xsd:integer)
- 2011 (xsd:integer)
- 2013 (xsd:integer)
|
| prop-fr:arxiv
| |
| prop-fr:auteur
|
- Cyril Nicaud (fr)
- Peter Linz (fr)
- Sven De Felice (fr)
- Janusz Brzozowski (fr)
- Cyril Nicaud (fr)
- Peter Linz (fr)
- Sven De Felice (fr)
- Janusz Brzozowski (fr)
|
| prop-fr:auteursOuvrage
|
- Marie-Pierre Béal et Olivier Carton (fr)
- Marie-Pierre Béal et Olivier Carton (fr)
|
| prop-fr:collection
|
- Annals of mathematics studies (fr)
- Lecture Notes in Computer Science (fr)
- Annals of mathematics studies (fr)
- Lecture Notes in Computer Science (fr)
|
| prop-fr:doi
|
- 10.100700 (xsd:double)
- 10.101600 (xsd:double)
- 10.110900 (xsd:double)
|
| prop-fr:isbn
|
- 2 (xsd:integer)
- 978 (xsd:integer)
|
| prop-fr:journal
|
- IEEE Transactions on Computers (fr)
- Theoretical Computer Science (fr)
- Acta Informatica (fr)
- Information Processing Letters (fr)
- IEEE Transactions on Computers (fr)
- Theoretical Computer Science (fr)
- Acta Informatica (fr)
- Information Processing Letters (fr)
|
| prop-fr:langue
|
- en (fr)
- fr (fr)
- en (fr)
- fr (fr)
|
| prop-fr:lienAuteur
|
- John Hopcroft (fr)
- Alfred Aho (fr)
- Edward F. Moore (fr)
- Jeffrey D. Ullman (fr)
- John Hopcroft (fr)
- Alfred Aho (fr)
- Edward F. Moore (fr)
- Jeffrey D. Ullman (fr)
|
| prop-fr:lieu
|
- New York (fr)
- Paris (fr)
- Princeton, N. J. (fr)
- Sudbury, MA (fr)
- New York (fr)
- Paris (fr)
- Princeton, N. J. (fr)
- Sudbury, MA (fr)
|
| prop-fr:lireEnLigne
| |
| prop-fr:mathReviews
|
- 603263 (xsd:integer)
- 1795249 (xsd:integer)
|
| prop-fr:mr
|
- 78059 (xsd:integer)
- 175719 (xsd:integer)
- 403320 (xsd:integer)
|
| prop-fr:nom
|
- Carton (fr)
- Moore (fr)
- Weiner (fr)
- Yu (fr)
- Aho (fr)
- Hopcroft (fr)
- Ullman (fr)
- Berstel (fr)
- Blum (fr)
- Boasson (fr)
- Fagnot (fr)
- Gries (fr)
- Knuutila (fr)
- Sakarovitch (fr)
- Séébold (fr)
- Salomaa (fr)
- Kameda (fr)
- Culik II (fr)
- Câmpeanu (fr)
- Leiss (fr)
- Carton (fr)
- Moore (fr)
- Weiner (fr)
- Yu (fr)
- Aho (fr)
- Hopcroft (fr)
- Ullman (fr)
- Berstel (fr)
- Blum (fr)
- Boasson (fr)
- Fagnot (fr)
- Gries (fr)
- Knuutila (fr)
- Sakarovitch (fr)
- Séébold (fr)
- Salomaa (fr)
- Kameda (fr)
- Culik II (fr)
- Câmpeanu (fr)
- Leiss (fr)
|
| prop-fr:numéro
|
- 1 (xsd:integer)
- 2 (xsd:integer)
- 3 (xsd:integer)
- 7 (xsd:integer)
|
| prop-fr:numéroD'édition
| |
| prop-fr:numéroDansCollection
|
- 34 (xsd:integer)
- 2214 (xsd:integer)
- 7907 (xsd:integer)
|
| prop-fr:pages
|
- 65 (xsd:integer)
- 97 (xsd:integer)
- 333 (xsd:integer)
|
| prop-fr:pagesTotales
|
- 198 (xsd:integer)
- 437 (xsd:integer)
- 816 (xsd:integer)
|
| prop-fr:passage
|
- 60 (xsd:integer)
- 129 (xsd:integer)
- 157 (xsd:integer)
- 179 (xsd:integer)
- 189 (xsd:integer)
- 323 (xsd:integer)
- 529 (xsd:integer)
|
| prop-fr:prénom
|
- Olivier (fr)
- Jacques (fr)
- Jean (fr)
- Karel (fr)
- Peter (fr)
- David (fr)
- John (fr)
- Luc (fr)
- Timo (fr)
- Isabelle (fr)
- Jeffrey D. (fr)
- Ernst (fr)
- John E. (fr)
- Norbert (fr)
- Patrice (fr)
- Edward F. (fr)
- Cezar (fr)
- Kai (fr)
- Alfred V. (fr)
- Sheng (fr)
- Tsunehiko (fr)
- Olivier (fr)
- Jacques (fr)
- Jean (fr)
- Karel (fr)
- Peter (fr)
- David (fr)
- John (fr)
- Luc (fr)
- Timo (fr)
- Isabelle (fr)
- Jeffrey D. (fr)
- Ernst (fr)
- John E. (fr)
- Norbert (fr)
- Patrice (fr)
- Edward F. (fr)
- Cezar (fr)
- Kai (fr)
- Alfred V. (fr)
- Sheng (fr)
- Tsunehiko (fr)
|
| prop-fr:sousTitre
|
- Méthodes et exercices corrigés (fr)
- Méthodes et exercices corrigés (fr)
|
| prop-fr:titre
|
- Théorie des automates (fr)
- An O implementation of the standard method for minimizing n-state finite automata (fr)
- An Introduction to Formal Languages and Automata (fr)
- Automata studies (fr)
- Describing an algorithm by Hopcroft (fr)
- Re-describing an algorithm by Hopcroft (fr)
- The Design and Analysis of Computer Algorithms (fr)
- Éléments de théorie des automates (fr)
- Succinct representation of regular languages by Boolean automata (fr)
- On the state minimization of nondeterministic finite automata (fr)
- Théorie des automates (fr)
- An O implementation of the standard method for minimizing n-state finite automata (fr)
- An Introduction to Formal Languages and Automata (fr)
- Automata studies (fr)
- Describing an algorithm by Hopcroft (fr)
- Re-describing an algorithm by Hopcroft (fr)
- The Design and Analysis of Computer Algorithms (fr)
- Éléments de théorie des automates (fr)
- Succinct representation of regular languages by Boolean automata (fr)
- On the state minimization of nondeterministic finite automata (fr)
|
| prop-fr:titreChapitre
|
- Gedanken-experiments on sequential machines (fr)
- Minimization of Automata (fr)
- Brzozowski Algorithm Is Generically Super-Polynomial for Deterministic Automata (fr)
- An algorithm for minimizing states in a finite automaton (fr)
- Canonical regular expressions and minimal state graphs for definite events (fr)
- State Complexity of Basic Operations on Finite Languages (fr)
- Gedanken-experiments on sequential machines (fr)
- Minimization of Automata (fr)
- Brzozowski Algorithm Is Generically Super-Polynomial for Deterministic Automata (fr)
- An algorithm for minimizing states in a finite automaton (fr)
- Canonical regular expressions and minimal state graphs for definite events (fr)
- State Complexity of Basic Operations on Finite Languages (fr)
|
| prop-fr:titreOuvrage
|
- 4 (xsd:integer)
- Developments in Language Theory - 17th International Conference (fr)
- Automata: from Mathematics to Applications (fr)
- Theory of machines and computations (fr)
- Proc. Sympos. Math. Theory of Automata (fr)
|
| prop-fr:volume
|
- 2 (xsd:integer)
- 13 (xsd:integer)
- 57 (xsd:integer)
- 100 (xsd:integer)
- 250 (xsd:integer)
|
| prop-fr:wikiPageUsesTemplate
| |
| prop-fr:zbl
| |
| prop-fr:éditeur
|
- dbpedia-fr:Addison-Wesley
- dbpedia-fr:Vuibert
- Princeton University Press (fr)
- Academic Press (fr)
- Springer-Verlag (fr)
- European Mathematical Society (fr)
- Jones & Bartlett Publishers (fr)
- Polytechnic Press of Polytechnic Inst. of Brooklyn, Brooklyn, N.Y. (fr)
|
| dct:subject
| |
| rdfs:comment
|
- En informatique théorique, et plus particulièrement en théorie des automates, la minimisation d'un automate fini déterministe est l'opération qui consiste à transformer un automate fini déterministe donné en un automate fini déterministe ayant le nombre minimal d'états et qui reconnaît le même langage rationnel. La minimisation a une importance pratique évidente par le gain d'espace qu'elle permet. Il existe plusieurs algorithmes pour effectuer cette opération de minimisation ; les plus usuels sont décrits pour la plupart dans les manuels traitant de théorie des automates. (fr)
- En informatique théorique, et plus particulièrement en théorie des automates, la minimisation d'un automate fini déterministe est l'opération qui consiste à transformer un automate fini déterministe donné en un automate fini déterministe ayant le nombre minimal d'états et qui reconnaît le même langage rationnel. La minimisation a une importance pratique évidente par le gain d'espace qu'elle permet. Il existe plusieurs algorithmes pour effectuer cette opération de minimisation ; les plus usuels sont décrits pour la plupart dans les manuels traitant de théorie des automates. (fr)
|
| rdfs:label
|
- Minimisation d'un automate fini déterministe (fr)
- Minimização de AFD (pt)
- Minimizzazione di DFA (it)
- Мінімізація ДСкА (uk)
- تصغير DFA (ar)
- 确定有限状态自动机最小化 (zh)
- Minimisation d'un automate fini déterministe (fr)
- Minimização de AFD (pt)
- Minimizzazione di DFA (it)
- Мінімізація ДСкА (uk)
- تصغير DFA (ar)
- 确定有限状态自动机最小化 (zh)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageWikiLink
of | |
| is oa:hasTarget
of | |
| is foaf:primaryTopic
of | |
