Mikołaj Bojańczyk

Mikołaj Bojańczyk, né en 1977, est un informaticien théoricien et logicien polonais, professeur à l'université de Varsovie.

Mikołaj Bojańczyk
Naissance
Nationalité Polonais
Domaines Théorie des automates, logique mathématique
Institutions Université de Varsovie
Formation Université de Varsovie
Directeur de thèse Igor Walukiewicz
Renommé pour Théorie des automates cheminants
Distinctions Prix Presburger
Site www.mimuw.edu.pl/~bojan/

Biographie scientifique

Bojańczyk obtient en 2004 un doctorat de l'université de Varsovie. Il passe l'année 2004-2005 à l'université Paris-Diderot. Il obtient une habilitation à l'université de Varsovie en 2008[1] et est professeur titulaire à cette université depuis 2014. Bojańczyk est le premier récipiendaire du prix Presburger en 2010[2]. Il a d'ailleurs réuni un certain nombre de documents sur Presburger[3].

Thèmes de recherche

Bojańczyk travaille sur l'interaction entre les formalismes logiques et les diverses familles d'automates finis. Il est connu pour ses contributions à la théorie des automates cheminants[4],[5] avec Thomas Colcombet (en), et pour de nombreuses autres contributions à la logique en théorie des automates[6],[7]. Il a travaillé sur le problème de la hauteur d'étoile : il présente une simplification de la preuve de la décidabilité[8], en 2015, article détaillé sur arxiv[9] en 2017. Il s'intéresse à la logique monadique du second ordre sur les graphes dans le cadre de la théorie de Courcelle, il étend la logique avec un quantificateur U pour pouvoir formuler des expressions, toujours sur les graphes ; il a introduit et étudié des langages réguliers sur les monads. Il étudie, dans une série d'articles, des data words et data trees, généralisations au cas d'alphabets infinis. Enfin, il développe, à l’université de Varsovie, un projet appelé Atoms, motivé initialement par l'étude d'automates sur les data words et data trees. Un livre est en cours de rédaction, disponible sur le site[10].

Notes et références
  1. (en) « Mikolaj Bojanczyk », sur le site du Mathematics Genealogy Project
  2. « Presburger Award », sur European Association for Theoretical Computer Science.
  3. Mojzesz Presburger à Varsovie.
  4. Mikołaj Bojańczyk et Thomas Colcombet, « Tree-walking automata cannot be determinized », Theoretical Computer Science, vol. 350, nos 2-3,‎ , p. 164–173 (DOI 10.1016/j.tcs.2005.10.031)
  5. Mikołaj Bojańczyk et Thomas Colcombet, « Tree-Walking Automata Do Not Recognize All Regular Languages », SIAM Journal on Computing, vol. 38, no 2,‎ , p. 658–701 (DOI 10.1137/050645427, lire en ligne)
  6. Mikołaj Bojańczyk et Paweł Parys, « XPath Evaluation in Linear Time », Journal of the ACM, vol. 58, no 4,‎ , p. 17:1–17:33 (DOI 10.1145/1989727.1989731, lire en ligne)
  7. Mikoaj Bojańczyk, Anca Muscholl, Thomas Schwentick et Luc Segoufin, « Two-variable Logic on Data Trees and XML Reasoning », Journal of the ACM, vol. 56, no 3,‎ , p. 13:1–13:48 (DOI 10.1145/1516512.1516515, lire en ligne)
  8. Mikolaj Bojanczyk, « Star Height via Games », ACM/IEEE Symposium on Logic in Computer,‎ , p. 214–219 (DOI 10.1109/LICS.2015.29)
  9. Star Height via Games
  10. Atom book.

Liens externes
  • Portail de l'informatique théorique
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.