Mikołaj Bojańczyk

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

modifier - modifier le code - modifier WikidataDocumentation du modèle

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

v · m
Lauréats du prix Presburger

Strategi Solo vs Squad di Free Fire: Cara Menang Mudah!