Emil Post - Définition

Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs est disponible ici.

Emil Leon Post (né le 11 février 1897, mort le 21 avril 1954) était un mathématicien américain né sur le territoire de l'actuelle Pologne dans une famille juive. Il est à l'origine du problème de correspondance de Post.

Il a également publié en 1921 une étude exhaustive des clones des algèbres à deux éléments.

Le problème de correspondance (La correspondance est un échange de courrier généralement prolongé sur une longue période. Le...) de Post

On part de deux suites finies U et V contenant le même nombre (La notion de nombre en linguistique est traitée à l’article « Nombre...) de mots finis sur un alphabet quelconque. Par exemple u1 = aba,u2 = b,u3 = a,u4 = ab,v1 = a,v2 = b,v3 = ababa,v4 = b.

On cherche une suite d'indices i1,i2,...in telle que la concaténation (Le terme concaténation (substantif féminin), du latin cum (« avec »)...) des u_{i_k} corresponde à celle des v_{i_k}. Ici la suite (1,2,3,2,1) est une solution puisque u1u2u3u2u1 = v1v2v3v2v1 = ababababa.

Le problème de correspondance de Post (en abrégé PCP) consiste à déterminer l'existence d'une telle suite. Il est indécidable en général : il ne peut pas exister d'algorithme capable de fournir une réponse pour des U et V arbitraires.

Page générée en 0.020 seconde(s) - site hébergé chez Contabo
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
A propos - Informations légales | Partenaire: HD-Numérique
Version anglaise | Version allemande | Version espagnole | Version portugaise