Thomas Colcombet

Thomas Colcombet
Thomas Colcombet
Born	March 6, 1975 (age 49)
Alma mater	University of Rennes 1
Known for	tree walking automata, Liquid War
Awards	Bronze medal of the CNRS (2010)
	Scientific career
Fields	Theoretical Computer Science ; Automata theory
Institutions	Paris Diderot University
Doctoral advisor	Didier Caucal

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[edit]

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[edit]

^ 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.
^ 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.
^ 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.
^ 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.

External links[edit]

Official website
Thomas Colcombet at DBLP Bibliography Server
Thomas Colcombet at the Mathematics Genealogy Project

[BojańczykColcombet2006-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.

[BojańczykColcombet2008-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.

[ColcombetZdanowski2009-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.

[1]

[2]

[3]

[4]