Publications

2012

Thomas Colcombet. Forms of Determinism for Automata. In STACS, 2012. Note: To appear. [pdf]

Thomas Colcombet. The Factorisation Forest Theorem. Note: To appear in the handbook ``Automata: from Mathematics to Applications'', 2012.

2011

Olivier Carton, Thomas Colcombet, and Gabriele Puppis. Regular Languages of Words over Countable Linear Orderings. In ICALP (2), pages 125-136, 2011. [pdf]

Thomas Colcombet. Green's Relations and Their Use in Automata Theory. In LATA, pages 1-21, 2011. [pdf]

Thomas Colcombet, Clemens Ley, and Gabriele Puppis. On the Use of Guards for Logics with Data. In MFCS, pages 243-255, 2011. [pdf]

Thomas Colcombet. Regular cost functions, Part I: logic and algebra over words. Note: Submitted, Special issue of ICALP09, 2011. [pdf]

Thomas Colcombet. Safra-like constructions for regular cost functions over finite words. Note: Unpublished, 2011.

2010

Thomas Colcombet. Factorisation Forests for Infinite Words and applications to countable scattered linear orderings. TCS, 411:751-764, 2010. Note: Selected papers of FCT 07. [pdf]

Thomas Colcombet, Denis Kuperberg, and Sylvain Lombardy. Regular Temporal Cost Functions. In ICALP (2), pages 563-574, 2010. [pdf]

Thomas Colcombet and Christof Löding. Regular cost functions over finite trees. In LICS, pages 70-79, 2010. [pdf]

2009

Mikolaj Bojanczyk and Thomas Colcombet. Bounds in $\omega$-regularity. LMCS, 2009. Note: To appear in the selected papers of LICS 06. [pdf]

Thomas Colcombet. The Theory of Stabilisation Monoids and Regular Cost Functions. In 36th ICALP, number 5556 of LNCS, Rhodos, pages 139-150, July 2009. SPRINGER. [pdf]

Thomas Colcombet and Konrad Zdanowski. A Tight Lower Bound for Determinization of Transition Labeled Büchi Automata. In 36th ICALP, number 5556 of LNCS, Rhodos, pages 151-162, July 2009. SPRINGER. [pdf]

Thomas Colcombet. Regular cost functions over words (draft). Note: This is a draft, not reviewed. All the algebra part can be found with a better presentation in the submitted 'Regular cost functions, Part I: logic and algebra over words', 2009. [pdf]

2008

Mikolaj Bojanczyk and Thomas Colcombet. Tree-Walking Automata Do Not Recognize All Regular Languages. SIAMjc, 38(2):658-701, 2008. Note: Selected papers of STOC 05. [doi:10.1137/050645427]

Thomas Colcombet and Christof Löding. The non-deterministic Mostowski hierarchy and distance-parity automata. In 35th ICALP, number 5126 of LNCS, Reykjavik, pages 398-409, 2008. SPRINGER. [pdf]

Thomas Colcombet and Christof öding. The Nesting-Depth of Disjunctive $\mu$-calculus for Tree Languages and the Limitedness Problem. In CSL, number 5213 of LNCS, Bertinoro, pages 416-430, 2008. SPRINGER. [pdf]

2007

Achim Blumensath, Thomas Colcombet, and Christof Löding. Logical Theories and Compatible Operations, volume Text in Logics and Games 2, pages 75-109. Amsterdam University Press, 2007. [pdf]

Thomas Colcombet and Christof Löding. Transforming structures by set interpretations. LMCS, 3-2(4), 2007. [pdf]

Thomas Colcombet. A combinatorial theorem for trees. In 34th ICALP, number 4596 of LNCS, Wroc\law, pages 901-912, 2007. SPRINGER. [pdf]

Thomas Colcombet. Factorisation forests for infinite words. In FCT 07, number 4639 of LNCS, Budapest, pages 226-237, 2007. SPRINGER. [pdf]

Thomas Colcombet. On Factorization Forests. Technical report hal-00125047, Irisa Rennes, 2007. [pdf]

2006

Mikolaj Bojanczyk and Thomas Colcombet. Tree-walking automata cannot be determinized. TCS, 350(2-3):164-173, 2006. Note: Selected papers of ICALP 04. [pdf]

Thomas Colcombet and Damian Niwinski. On the positional determinacy of edge-labeled games. TCS, 352(1-3):190-196, 2006. [pdf]

Mikolaj Bojanczyk and Thomas Colcombet. Bounds in $\omega$-regularity. In LICS 06, pages 285-296, 2006. [pdf]

Thomas Colcombet and Christof Löding. Transforming structures by set interpretations. Technical report AIB-2006-07, RWTH Aachen, 2006. [pdf]

2005

Mikolaj Bojanczyk and Thomas Colcombet. Tree-Walking Automata Do Not Recognize All Regular Languages. In STOC 05, Baltimore, pages 234-243, 2005. [pdf]

2004

Thomas Colcombet. Propriétés et représentation de structures infinies (properties and representation of infinite structures). PhD thesis, Université Rennes I, March 2004. [pdf]

Mikolaj Bojanczyk and Thomas Colcombet. Tree-Walking Automata Cannot Be Determinized. In 31th ICALP, number 3142 of LNCS, Turku, pages 246-256, 2004. SPRINGER. Note: Best paper award, track B. [pdf]

Thomas Colcombet. Equational presentations of tree-automatic structures. In WASL 04, Auckland, 2004. [pdf]

Thomas Colcombet and Christof Löding. On the Expressiveness of Deterministic Transducers over Infinite Trees. In STACS 04, number 2996 of LNCS, Montpellier, pages 428-439, March 2004. SPRINGER. [pdf]

2003

Arnaud Carayol and Thomas Colcombet. On Equivalent Representations of Infinite Structures. In 30th ICALP, number 2719 of LNCS, Eindhoven, July 2003. SPRINGER. [pdf]

2002

Thomas Colcombet. Rewriting in the partial algebra of typed terms modulo AC. ENTCS, 68(6), 2002. [pdf]

Thomas Colcombet. On Families of Graphs Having a Decidable First Order Theory with Reachability. In 29th ICALP, number 2380 of LNCS, Malaga, pages 98-109, July 2002. Springer. Note: Best student paper award, track B. [pdf]

2000

Thomas Colcombet and Pascal Fradet. Enforcing Trace Properties by Program Transformation. In POPL 00, Boston, pages 54-66, January 2000. ACM. [pdf]