"Support de cours du Master Parisien de Recherche en Informatique"@fr . . "413"^^ . "10.1016"^^ . "Sch\u00FCtzenberger"@fr . . "6538771"^^ . "Imre"@fr . . . . . "Finite semigroups and recognizable languages: an introduction"@fr . "Gomes"@fr . "Pin"@fr . "Jean-\u00C9ric"@fr . "Springer-Verlag"@fr . "Varieties of formal languages"@fr . "1995"^^ . "Finite Automata"@fr . . "310"^^ . . "190"^^ . "401604"^^ . "H. Brakhage"@fr . "181714119"^^ . "1986"^^ . . . "466"^^ . "Eilenberg"@fr . . . "NATO Advanced Study Institute Series C"@fr . "978"^^ . . "95"^^ . . "Semigroups, Formal Languages and Groups"@fr . "J. Fountain"@fr . "2012"^^ . "GomesPinSilva"@fr . "2002"^^ . "2003"^^ . . "Marcel-Paul"@fr . "Lecture Notes in Computer Science"@fr . "Mathematical Foundations of Automata Theory"@fr . . "Gracinda M. S."@fr . "214"^^ . . . "1965"^^ . "Mark V."@fr . "--06-20"^^ . "Chapman and Hall/CRC"@fr . "Pure and Applied Mathematics"@fr . ": Coimbra, Portugal, May-July 2001"@fr . . "19"^^ . "320"^^ . . "1976"^^ . . "8"^^ . "Semigroups, algorithms, automata, and languages"@fr . "Dordrecht"@fr . . . . . "Kluwer Academic Publishers"@fr . "Samuel Eilenberg"@fr . "En informatique th\u00E9orique, et notamment en th\u00E9orie de langages rationnels, le th\u00E9or\u00E8me des vari\u00E9t\u00E9s d'Eilenberg, aussi appel\u00E9 th\u00E9or\u00E8me des vari\u00E9t\u00E9s d'Eilenberg et Sch\u00FCtzenberger d'apr\u00E8s leurs d\u00E9couvreurs Samuel Eilenberg et Marcel-Paul Sch\u00FCtzenberger, \u00E9tablit une correspondance entre vari\u00E9t\u00E9s de langages formels rationnels et (pseudo-) vari\u00E9t\u00E9s de mono\u00EFdes finis. Ce th\u00E9or\u00E8me des vari\u00E9t\u00E9s, \u00E9tabli dans les ann\u00E9es 1970 et dont l'expos\u00E9 syst\u00E9matique occupe une large part du volume B du trait\u00E9 d'Eilenberg, constitue la base d'une th\u00E9orie alg\u00E9brique des langages rationnels qui s'est d\u00E9velopp\u00E9e consid\u00E9rablement depuis. Il fournit le cadre qui permet de mettre en relation les propri\u00E9t\u00E9s alg\u00E9briques de mono\u00EFdes et les propri\u00E9t\u00E9s combinatoires des langages rationnels."@fr . "Simon"@fr . "1975"^^ . . "York, 1993"@fr . "On finite monoids having only trivial subgroups"@fr . . "Boca Raton/London/New York etc."@fr . . "En informatique th\u00E9orique, et notamment en th\u00E9orie de langages rationnels, le th\u00E9or\u00E8me des vari\u00E9t\u00E9s d'Eilenberg, aussi appel\u00E9 th\u00E9or\u00E8me des vari\u00E9t\u00E9s d'Eilenberg et Sch\u00FCtzenberger d'apr\u00E8s leurs d\u00E9couvreurs Samuel Eilenberg et Marcel-Paul Sch\u00FCtzenberger, \u00E9tablit une correspondance entre vari\u00E9t\u00E9s de langages formels rationnels et (pseudo-) vari\u00E9t\u00E9s de mono\u00EFdes finis. Ce th\u00E9or\u00E8me des vari\u00E9t\u00E9s, \u00E9tabli dans les ann\u00E9es 1970 et dont l'expos\u00E9 syst\u00E9matique occupe une large part du volume B du trait\u00E9 d'Eilenberg, constitue la base d'une th\u00E9orie alg\u00E9brique des langages rationnels qui s'est d\u00E9velopp\u00E9e consid\u00E9rablement depuis. Il fournit le cadre qui permet de mettre en relation les propri\u00E9t\u00E9s alg\u00E9briques de mono\u00EFdes et les propri\u00E9t\u00E9s combinatoires des langages rationnels. Un exemple c\u00E9l\u00E8bre de cette correspondance, \u00E9tabli par Sch\u00FCtzenberger en 1965, donc avant la formulation du th\u00E9or\u00E8me des vari\u00E9t\u00E9s, est le th\u00E9or\u00E8me de qui caract\u00E9rise les langages rationnels \u00AB sans \u00E9toile \u00BB par la propri\u00E9t\u00E9 que leur mono\u00EFde syntaxique n'a que des \u00AB sous-groupes triviaux \u00BB, en d'autres termes, les -classes qui sont des groupes sont des singletons (mono\u00EFdes ap\u00E9riodiques finis). Un autre r\u00E9sultat de cette nature est d\u00FB \u00E0 Imre Simon : un langage rationnel est testable par morceaux si et seulement si son mono\u00EFde syntaxique est -trivial, c'est-\u00E0-dire sa relation est l'identit\u00E9. Il faut noter tout de suite que le th\u00E9or\u00E8me des vari\u00E9t\u00E9s ne g\u00E9n\u00E9ralise pas ces r\u00E9sultats, et en particulier n'en fournit pas de preuve, mais permet de bien les formuler dans un cadre appropri\u00E9. La notion de vari\u00E9t\u00E9 de mono\u00EFdes finis utilis\u00E9e dans l'\u00E9nonc\u00E9 diff\u00E8re de la notion classique de vari\u00E9t\u00E9 d'alg\u00E8bres par sa d\u00E9finition et ses propri\u00E9t\u00E9s : une vari\u00E9t\u00E9 de mono\u00EFdes finis est d\u00E9finie comme \u00E9tant notamment ferm\u00E9es par produit direct fini, alors qu'une vari\u00E9t\u00E9 d'alg\u00E8bres est d\u00E9fini par des \u00E9quations, et c'est le th\u00E9or\u00E8me HSP de Birkhoff qui \u00E9tablit l'\u00E9quivalence entre d\u00E9finition par \u00E9quations et fermeture par produit direct quelconque. Pour marquer cette diff\u00E9rence, les vari\u00E9t\u00E9s de mono\u00EFdes finis ont \u00E9t\u00E9 appel\u00E9es pseudo-vari\u00E9t\u00E9s. Une autre diff\u00E9rence est que les vari\u00E9t\u00E9s de mono\u00EFdes finis ne sont pas toujours d\u00E9finissables par des \u00E9quations. L'\u00E9tude des \u00E9quations a conduit d'ailleurs \u00E0 une formulation plus g\u00E9n\u00E9rale d'\u00E9quations."@fr . "Samuel"@fr . "515"^^ . . . . "en"@fr . . "Th\u00E9or\u00E8me des vari\u00E9t\u00E9s d'Eilenberg"@fr . "Piecewise testable events"@fr . . "Advances in Math."@fr . "2"^^ . "Silva"@fr . "Marcel-Paul Sch\u00FCtzenberger"@fr . "3"^^ . . . "33"^^ . "19425"^^ . . . "xiii+387"@fr . . . "x+138"@fr . . "Information and Control"@fr . . "0"^^ . "Proceedings 2nd GI Conference"@fr . . "1"^^ . . . "Lawson"@fr . . "Pedro V."@fr . "89"^^ . . "530383"^^ . "59"^^ . "On pseudovarieties"@fr . . "1"^^ . "Automata, Languages and Machines, Vol. B"@fr . . . "Plenum Publishing Corp."@fr . "Foundations of Computer Science"@fr . . .