Thomas Colcombet Explained

Thomas Colcombet
Birth Date:	March 6, 1975
Field:	Theoretical Computer Science Automata theory
Work Institution:	Paris Diderot University
Alma Mater:	University of Rennes 1
Doctoral Advisor:	Didier Caucal
Known For:	tree walking automata, Liquid War
Prizes:	Bronze medal of the CNRS (2010)

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.

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.

Notes and References

1. Bojańczyk. Mikołaj. Colcombet. Thomas. Tree-walking automata cannot be determinized. Theoretical Computer Science. 350. 2–3. 2006. 164–173. 0304-3975. 10.1016/j.tcs.2005.10.031. free.
2. Bojańczyk. Mikołaj. Colcombet. Thomas. Tree-Walking Automata Do Not Recognize All Regular Languages. SIAM Journal on Computing. 38. 2. 2008. 658–701. 0097-5397. 10.1137/050645427. 10.1.1.100.7065.
3. Colcombet. Thomas. Fijalkow. Nathanaël. The Bridge Between Regular Cost Functions and Omega-Regular Languages. 2016. ICALP 2016. 43rd International Colloquium on Automata, Languages, and Programming. 55. 126:1126:13. Leibniz International Proceedings in Informatics (LIPIcs). 978-3-95977-013-2. 10.4230/LIPIcs.ICALP.2016.126. free .
4. Book: Colcombet. Thomas. Automata, Languages and Programming. Zdanowski. Konrad. A Tight Lower Bound for Determinization of Transition Labeled Büchi Automata. 5556. 2009. 151–162. 0302-9743. 10.1007/978-3-642-02930-1_13. Lecture Notes in Computer Science. 978-3-642-02929-5.