Thomas Colcombet

Thomas Colcombet
Born (1975-03-06) March 6, 1975
Residence  France
Fields Theoretical Computer Science
Automata theory
Institutions Paris Diderot University
Alma mater University of Rennes 1
Doctoral advisor Didier Caucal
Known for tree walking automata
Notable awards Bronze medal of the CNRS (2010)

Thomas Colcombet (b. 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.

References

  1. ↑ Bojańczyk, Mikołaj; Colcombet, Thomas (2006). "Tree-walking automata cannot be determinized". Theoretical Computer Science. 350 (2-3): 164–173. ISSN 0304-3975. doi:10.1016/j.tcs.2005.10.031.
  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. ISSN 0097-5397. doi:10.1137/050645427.
  3. ↑ Colcombet, Thomas; Fijalkow, Nathanaël (2016). "The Bridge Between Regular Cost Functions and Omega-Regular Languages". ISBN 978-3-95977-013-2. doi:10.4230/LIPIcs.ICALP.2016.126.
  4. ↑ Colcombet, Thomas; Zdanowski, Konrad (2009). "A Tight Lower Bound for Determinization of Transition Labeled Büchi Automata". 5556: 151–162. ISSN 0302-9743. doi:10.1007/978-3-642-02930-1_13.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.