| Property |
Value |
| dbo:abstract
|
- En informatique théorique, et notamment en théorie de langages rationnels, le théorème des variétés d'Eilenberg, aussi appelé théorème des variétés d'Eilenberg et Schützenberger d'après leurs découvreurs Samuel Eilenberg et Marcel-Paul Schützenberger, établit une correspondance entre variétés de langages formels rationnels et (pseudo-) variétés de monoïdes finis. Ce théorème des variétés, établi dans les années 1970 et dont l'exposé systématique occupe une large part du volume B du traité d'Eilenberg, constitue la base d'une théorie algébrique des langages rationnels qui s'est développée considérablement depuis. Il fournit le cadre qui permet de mettre en relation les propriétés algébriques de monoïdes et les propriétés combinatoires des langages rationnels. Un exemple célèbre de cette correspondance, établi par Schützenberger en 1965, donc avant la formulation du théorème des variétés, est le théorème de qui caractérise les langages rationnels « sans étoile » par la propriété que leur monoïde syntaxique n'a que des « sous-groupes triviaux », en d'autres termes, les -classes qui sont des groupes sont des singletons (monoïdes apériodiques finis). Un autre résultat de cette nature est dû à Imre Simon : un langage rationnel est testable par morceaux si et seulement si son monoïde syntaxique est -trivial, c'est-à-dire sa relation est l'identité. Il faut noter tout de suite que le théorème des variétés ne généralise pas ces résultats, et en particulier n'en fournit pas de preuve, mais permet de bien les formuler dans un cadre approprié. La notion de variété de monoïdes finis utilisée dans l'énoncé diffère de la notion classique de variété d'algèbres par sa définition et ses propriétés : une variété de monoïdes finis est définie comme étant notamment fermées par produit direct fini, alors qu'une variété d'algèbres est défini par des équations, et c'est le théorème HSP de Birkhoff qui établit l'équivalence entre définition par équations et fermeture par produit direct quelconque. Pour marquer cette différence, les variétés de monoïdes finis ont été appelées pseudo-variétés. Une autre différence est que les variétés de monoïdes finis ne sont pas toujours définissables par des équations. L'étude des équations a conduit d'ailleurs à une formulation plus générale d'équations. (fr)
- En informatique théorique, et notamment en théorie de langages rationnels, le théorème des variétés d'Eilenberg, aussi appelé théorème des variétés d'Eilenberg et Schützenberger d'après leurs découvreurs Samuel Eilenberg et Marcel-Paul Schützenberger, établit une correspondance entre variétés de langages formels rationnels et (pseudo-) variétés de monoïdes finis. Ce théorème des variétés, établi dans les années 1970 et dont l'exposé systématique occupe une large part du volume B du traité d'Eilenberg, constitue la base d'une théorie algébrique des langages rationnels qui s'est développée considérablement depuis. Il fournit le cadre qui permet de mettre en relation les propriétés algébriques de monoïdes et les propriétés combinatoires des langages rationnels. Un exemple célèbre de cette correspondance, établi par Schützenberger en 1965, donc avant la formulation du théorème des variétés, est le théorème de qui caractérise les langages rationnels « sans étoile » par la propriété que leur monoïde syntaxique n'a que des « sous-groupes triviaux », en d'autres termes, les -classes qui sont des groupes sont des singletons (monoïdes apériodiques finis). Un autre résultat de cette nature est dû à Imre Simon : un langage rationnel est testable par morceaux si et seulement si son monoïde syntaxique est -trivial, c'est-à-dire sa relation est l'identité. Il faut noter tout de suite que le théorème des variétés ne généralise pas ces résultats, et en particulier n'en fournit pas de preuve, mais permet de bien les formuler dans un cadre approprié. La notion de variété de monoïdes finis utilisée dans l'énoncé diffère de la notion classique de variété d'algèbres par sa définition et ses propriétés : une variété de monoïdes finis est définie comme étant notamment fermées par produit direct fini, alors qu'une variété d'algèbres est défini par des équations, et c'est le théorème HSP de Birkhoff qui établit l'équivalence entre définition par équations et fermeture par produit direct quelconque. Pour marquer cette différence, les variétés de monoïdes finis ont été appelées pseudo-variétés. Une autre différence est que les variétés de monoïdes finis ne sont pas toujours définissables par des équations. L'étude des équations a conduit d'ailleurs à une formulation plus générale d'équations. (fr)
|
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 19425 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| prop-fr:année
|
- 1965 (xsd:integer)
- 1975 (xsd:integer)
- 1976 (xsd:integer)
- 1986 (xsd:integer)
- 1995 (xsd:integer)
- 2002 (xsd:integer)
- 2003 (xsd:integer)
- 2012 (xsd:integer)
|
| prop-fr:auteursOuvrage
|
- H. Brakhage (fr)
- J. Fountain (fr)
- H. Brakhage (fr)
- J. Fountain (fr)
|
| prop-fr:collection
|
- Lecture Notes in Computer Science (fr)
- Pure and Applied Mathematics (fr)
- Foundations of Computer Science (fr)
- NATO Advanced Study Institute Series C (fr)
- Lecture Notes in Computer Science (fr)
- Pure and Applied Mathematics (fr)
- Foundations of Computer Science (fr)
- NATO Advanced Study Institute Series C (fr)
|
| prop-fr:doi
| |
| prop-fr:id
|
- GomesPinSilva (fr)
- GomesPinSilva (fr)
|
| prop-fr:isbn
|
- 0 (xsd:integer)
- 1 (xsd:integer)
- 978 (xsd:integer)
|
| prop-fr:langue
| |
| prop-fr:lienAuteur
|
- Samuel Eilenberg (fr)
- Marcel-Paul Schützenberger (fr)
- Samuel Eilenberg (fr)
- Marcel-Paul Schützenberger (fr)
|
| prop-fr:lieu
|
- Dordrecht (fr)
- Boca Raton/London/New York etc. (fr)
- Dordrecht (fr)
- Boca Raton/London/New York etc. (fr)
|
| prop-fr:lireEnLigne
| |
| prop-fr:mathReviews
|
- 89 (xsd:integer)
- 530383 (xsd:integer)
|
| prop-fr:mr
| |
| prop-fr:nom
|
- Pin (fr)
- Simon (fr)
- Silva (fr)
- Lawson (fr)
- Eilenberg (fr)
- Gomes (fr)
- Schützenberger (fr)
- Pin (fr)
- Simon (fr)
- Silva (fr)
- Lawson (fr)
- Eilenberg (fr)
- Gomes (fr)
- Schützenberger (fr)
|
| prop-fr:numéro
|
- 2 (xsd:integer)
- 3 (xsd:integer)
|
| prop-fr:numéroDansCollection
|
- 33 (xsd:integer)
- 59 (xsd:integer)
- 466 (xsd:integer)
|
| prop-fr:pages
|
- 190 (xsd:integer)
- 413 (xsd:integer)
|
| prop-fr:pagesTotales
|
- 310 (xsd:integer)
- 320 (xsd:integer)
- 515 (xsd:integer)
- x+138 (fr)
- xiii+387 (fr)
|
| prop-fr:passage
|
- 1 (xsd:integer)
- 95 (xsd:integer)
- 214 (xsd:integer)
|
| prop-fr:prénom
|
- Samuel (fr)
- Imre (fr)
- Jean-Éric (fr)
- Pedro V. (fr)
- Mark V. (fr)
- Marcel-Paul (fr)
- Gracinda M. S. (fr)
- Samuel (fr)
- Imre (fr)
- Jean-Éric (fr)
- Pedro V. (fr)
- Mark V. (fr)
- Marcel-Paul (fr)
- Gracinda M. S. (fr)
|
| prop-fr:présentationEnLigne
| |
| prop-fr:périodique
|
- Information and Control (fr)
- Advances in Math. (fr)
- Information and Control (fr)
- Advances in Math. (fr)
|
| prop-fr:sousTitre
|
- : Coimbra, Portugal, May-July 2001 (fr)
- : Coimbra, Portugal, May-July 2001 (fr)
|
| prop-fr:sousTitreOuvrage
|
- York, 1993 (fr)
- York, 1993 (fr)
|
| prop-fr:titre
|
- Mathematical Foundations of Automata Theory (fr)
- On finite monoids having only trivial subgroups (fr)
- Automata, Languages and Machines, Vol. B (fr)
- Finite Automata (fr)
- On pseudovarieties (fr)
- Semigroups, algorithms, automata, and languages (fr)
- Varieties of formal languages (fr)
- Mathematical Foundations of Automata Theory (fr)
- On finite monoids having only trivial subgroups (fr)
- Automata, Languages and Machines, Vol. B (fr)
- Finite Automata (fr)
- On pseudovarieties (fr)
- Semigroups, algorithms, automata, and languages (fr)
- Varieties of formal languages (fr)
|
| prop-fr:titreChapitre
|
- Piecewise testable events (fr)
- Finite semigroups and recognizable languages: an introduction (fr)
- Piecewise testable events (fr)
- Finite semigroups and recognizable languages: an introduction (fr)
|
| prop-fr:titreOuvrage
|
- Proceedings 2nd GI Conference (fr)
- Semigroups, Formal Languages and Groups (fr)
- Proceedings 2nd GI Conference (fr)
- Semigroups, Formal Languages and Groups (fr)
|
| prop-fr:volume
|
- 8 (xsd:integer)
- 19 (xsd:integer)
|
| prop-fr:wikiPageUsesTemplate
| |
| prop-fr:éditeur
| |
| dct:subject
| |
| rdfs:comment
|
- En informatique théorique, et notamment en théorie de langages rationnels, le théorème des variétés d'Eilenberg, aussi appelé théorème des variétés d'Eilenberg et Schützenberger d'après leurs découvreurs Samuel Eilenberg et Marcel-Paul Schützenberger, établit une correspondance entre variétés de langages formels rationnels et (pseudo-) variétés de monoïdes finis. Ce théorème des variétés, établi dans les années 1970 et dont l'exposé systématique occupe une large part du volume B du traité d'Eilenberg, constitue la base d'une théorie algébrique des langages rationnels qui s'est développée considérablement depuis. Il fournit le cadre qui permet de mettre en relation les propriétés algébriques de monoïdes et les propriétés combinatoires des langages rationnels. (fr)
- En informatique théorique, et notamment en théorie de langages rationnels, le théorème des variétés d'Eilenberg, aussi appelé théorème des variétés d'Eilenberg et Schützenberger d'après leurs découvreurs Samuel Eilenberg et Marcel-Paul Schützenberger, établit une correspondance entre variétés de langages formels rationnels et (pseudo-) variétés de monoïdes finis. Ce théorème des variétés, établi dans les années 1970 et dont l'exposé systématique occupe une large part du volume B du traité d'Eilenberg, constitue la base d'une théorie algébrique des langages rationnels qui s'est développée considérablement depuis. Il fournit le cadre qui permet de mettre en relation les propriétés algébriques de monoïdes et les propriétés combinatoires des langages rationnels. (fr)
|
| rdfs:label
|
- Théorème des variétés d'Eilenberg (fr)
- Théorème des variétés d'Eilenberg (fr)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageWikiLink
of | |
| is oa:hasTarget
of | |
| is foaf:primaryTopic
of | |
