Mikołaj Bojańczyk

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

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

  • icône décorative Portail de l'informatique théorique
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons – Attribution – Partage à l’identique. Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.