Thomas Colcombet

Thomas Colcombet (born March 6, 1975) is a French theoretical computer scientist known for settling major open problems on tree walking automata[1][2] jointly with Mikołaj Bojańczyk. Colcombet is currently a CNRS Research Director at Paris Diderot University.

Thomas Colcombet
Born (1975-03-06) March 6, 1975
Alma materUniversity of Rennes 1
Known fortree walking automata, Liquid War
AwardsBronze medal of the CNRS (2010)
Scientific career
FieldsTheoretical Computer Science
Automata theory
InstitutionsParis Diderot University
Doctoral advisorDidier Caucal

Biography

Colcombet earned his undergraduate degree from École normale supérieure de Lyon (2000) and his doctorate from University of Rennes 1 (2004). Since 2004, he is a CNRS researcher, and a Research Director since 2016. He received the CNRS Bronze Medal in 2010.

Besides his work on tree walking automata, Colcombet contributed to ω-automata,[3] particularly to state complexity of Büchi automata,[4] and to various topics in logic in computer science.

He was involved in the development of the videogame Liquid War.

References
  1. Bojańczyk, Mikołaj; Colcombet, Thomas (2006). "Tree-walking automata cannot be determinized". Theoretical Computer Science. 350 (2–3): 164–173. doi:10.1016/j.tcs.2005.10.031. ISSN 0304-3975.
  2. Bojańczyk, Mikołaj; Colcombet, Thomas (2008). "Tree-Walking Automata Do Not Recognize All Regular Languages". SIAM Journal on Computing. 38 (2): 658–701. CiteSeerX 10.1.1.100.7065. doi:10.1137/050645427. ISSN 0097-5397.
  3. Colcombet, Thomas; Fijalkow, Nathanaël (2016). "The Bridge Between Regular Cost Functions and Omega-Regular Languages". 43rd International Colloquium on Automata, Languages, and Programming. ICALP 2016. Leibniz International Proceedings in Informatics (LIPIcs). Vol. 55. pp. 126:1–126:13. doi:10.4230/LIPIcs.ICALP.2016.126. ISBN 978-3-95977-013-2.
  4. Colcombet, Thomas; Zdanowski, Konrad (2009). "A Tight Lower Bound for Determinization of Transition Labeled Büchi Automata". Automata, Languages and Programming. Lecture Notes in Computer Science. Vol. 5556. pp. 151–162. doi:10.1007/978-3-642-02930-1_13. ISBN 978-3-642-02929-5. ISSN 0302-9743.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.