Róbert Szelepcsényi

Róbert Szelepcsényi

Biographie

Naissance	19 août 1966 (58 ans) Žilina
Nationalité	slovaque
Formation	Université Comenius de Bratislava Université de Chicago Université de Rochester
Activités	Mathématicien, informaticien, ingénieur

Autres informations

Distinction	Prix Gödel (1995)

modifier - modifier le code - modifier Wikidata

Róbert Szelepcsényi, né le 19 août 1966 à Žilina en Tchécoslovaquie (aujourd'hui en Slovaquie), est un scientifique slovaque d'origine hongroise^[1].

Biographie

Encore étudiant à la Faculté de mathématique, physique et informatique de l'université Comenius de Bratislava, il démontre en 1987^[2], et indépendamment de Neil Immerman, ce qui est connu maintenant sous le nom de théorème d'Immerman-Szelepcsényi. Ce résultat leur a valu l'obtention en 1995 du prix Gödel décerné conjointement par l'ACM et l'EATCS ^[3].

Le théorème dit qu'une machine de Turing non déterministe peut résoudre le complémentaire d'un problème en utilisant la même quantité de place que pour le problème initial. Pour la complexité en temps, la même question en est encore ouverte (en 2010), mais on admet généralement qu'un tel énoncé n'existe pas dans ce cas.

En 1993, Róbert Szelepcsényi obtient une maîtrise universitaire ès sciences (M.S.) à l'université de Rochester^[4]. Il passe quelque temps en études en vue du Ph.D. à l'université de Chicago^[5]. En septembre 1999, il est à l'Académie slovaque des sciences^[4]. Un dernier article scientifique de Szelepcsényi paraît en 1999.

Notes et références

1. D'après Milan Strhan et David P. Daniel, Slovakia and the Slovaks : A Concise Encyclopedia, Bratislava, Encyclopedical Institute of the Slovak Academy of Sciences, 1994 (ISBN 9788085584110, lire en ligne), p. 637, il est peut-être le fils du compositeur Jan Szelepcsényi (cité par IMDB) né le 5 octobre 1937 à Žilina.
2. Róbert Szelepcsényi, « The Method of Forced Enumeration for Nondeterministic Automata ». Acta Informatica vol. 26, n^o 3, 1988, pages 279-284. Une prépublication, de même titre, paraît dans le Bulletin de l'EATCS, 1887.
3. Citation du prix Gödel 1995 sur ACM.
4. Étudiants de l'Université de Rochester « Copie archivée » (version du 4 janvier 2013 sur Internet Archive).
5. Liste des anciens étudiants du groupe de théorie

Source de la traduction

(de) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en allemand intitulé « Róbert Szelepcsényi » (voir la liste des auteurs).

Liens externes

• Ressource relative à la recherche :
  • Digital Bibliography & Library Project