Mikołaj Bojańczyk

Informaticien théorique polonais et logicien

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

Mikołaj Bojańczyk
une illustration sous licence libre serait bienvenue
Biographie
Naissance
(47 ans)
Nationalité
Domicile
Formation
Activités
Autres informations
A travaillé pour
Directeurs de thèse
Igor Walukiewicz (d), Andrzej Włodzimierz Mostowski (d)Voir et modifier les données sur Wikidata
Site web
Distinction

Biographie scientifique

modifier

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

modifier

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

modifier
  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

modifier