2013
| [1] | T. Colcombet, “The factorisation forest theorem.” To appear in the handbook “Automata: from Mathematics to Applications”, 2013. [ bib ] |
| [2] | T. Colcombet, “Regular cost functions, part I: logic and algebra over words,” Logical Methods in Computer Science, p. 47, 2013. To appear. [ bib | pdf ] |
| [3] | T. Colcombet and L. Daviaud, “Approximate comparison of distance automata,” in STACS 2013: 30th International Symposium on Theoretical Aspects of Computer Science (N. Portier and T. Wilke, eds.), vol. 20 of LIPIcs, pp. 574-585, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2013. [ bib | pdf ] |
| [4] | T. Colcombet, “Composition with algebra in the background,” in CSR, Lecture Notes in Computer Science, Springer, 2013. [ bib | pdf ] |
| [5] | T. Colcombet, C. Löding, D. Kuperberg, and M. V. Boom, “Deciding the weak definability of büchi definable tree languages.” in preparation, 2013. [ bib ] |
| [6] | T. Colcombet, “Cost functions with several orders of magnitudes and the use of relative internal set theory,” in LICS, 2013. [ bib ] |
| [7] | T. Colcombet, S. Göller, and A. Manuel, “Uniformization results on regular cost functions.” Submitted, 2013. [ bib ] |
| [8] | T. Colcombet and A. Manuel, “mu-calculus on data words.” Submitted, 2013. [ bib ] |
| [9] | A. Blumensath, T. Colcombet, D. Kuperberg, and M. V. Boom, “Two-way cost automata and cost logics over infinite trees.” Submitted, 2013. [ bib ] |
| [10] | A. Blumensath, O. Carton, and T. Colcombet, “Asymptotic monadic second-order logic.” Submitted, 2013. [ bib ] |
| [11] | T. Colcombet, “Fonctions régulières de coût.” Habilitation thesis, in french, 2013. [ bib | pdf ] |
2012
| [1] | T. Colcombet, “Forms of determinism for automata,” in STACS 2012: 29th International Symposium on Theoretical Aspects of Computer Science (C. Dürr and T. Wilke, eds.), vol. 14 of LIPIcs, pp. 1-23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2012. [ bib | pdf ] |
2011
| [1] | T. Colcombet, “Safra-like constructions for regular cost functions over finite words.” Unpublished, 2011. [ bib ] |
| [2] | O. Carton, T. Colcombet, and G. Puppis, “Regular languages of words over countable linear orderings,” in ICALP 2011 (2): Automata, Languages and Programming - 38th International Colloquium (L. Aceto, M. Henzinger, and J. Sgall, eds.), vol. 6756 of Lecture Notes in Computer Science, pp. 125-136, Springer, 2011. [ bib | pdf ] |
| [3] | T. Colcombet, C. Ley, and G. Puppis, “On the use of guards for logics with data,” in MFCS 2011: Mathematical Foundations of Computer Science (F. Murlak and P. Sankowski, eds.), vol. 6907 of Lecture Notes in Computer Science, pp. 243-255, Springer, 2011. [ bib | pdf ] |
| [4] | T. Colcombet, “Green's relations and their use in automata theory,” in LATA 2011: Language and Automata Theory and Applications - 5th International Conference (A. H. Dediu, S. Inenaga, and C. Martín-Vide, eds.), vol. 6638 of Lecture Notes in Computer Science, pp. 1-21, Springer, 2011. Invited lecture. [ bib | pdf ] |
2010
| [1] | T. Colcombet, D. Kuperberg, and S. Lombardy, “Regular temporal cost functions,” in ICALP 2010 (2): Automata, Languages and Programming, 37th International Colloquium (S. Abramsky, C. Gavoille, C. Kirchner, F. Meyer auf der Heide, and P. G. Spirakis, eds.), vol. 6199 of Lecture Notes in Computer Science, pp. 563-574, Springer, 2010. [ bib | pdf ] |
| [2] | T. Colcombet and C. Löding, “Regular cost functions over finite trees,” in LICS 2010: 5th Annual IEEE Symposium on Logic in Computer Science, pp. 70-79, 2010. [ bib | pdf ] |
| [3] | T. Colcombet, “Factorisation forests for infinite words and applications to countable scattered linear orderings,” Theoretical Computer Science, vol. 411, pp. 751-764, 2010. Selected papers of FCT 07. [ bib | pdf ] |
2009
| [1] | T. Colcombet, “The theory of stabilisation monoids and regular cost functions,” in ICALP 2009 (2): Automata, Languages and Programming, 36th International Colloquium (S. Albers, A. Marchetti-Spaccamela, Y. Matias, S. E. Nikoletseas, and W. Thomas, eds.), vol. 5556 of Lecture Notes in Computer Science, pp. 139-150, Springer, 2009. [ bib | pdf ] |
| [2] | T. Colcombet and K. Zdanowski, “A tight lower bound for determinization of transition labeled Büchi automata,” in ICALP 2009 (2): Automata, Languages and Programming, 36th International Colloquium (S. Albers, A. Marchetti-Spaccamela, Y. Matias, S. E. Nikoletseas, and W. Thomas, eds.), vol. 5556 of Lecture Notes in Computer Science, pp. 151-162, Springer, 2009. [ bib | pdf ] |
| [3] | M. Bojańczyk and T. Colcombet, “Bounds in ω-regularity,” Logical Methods in Computer Science, 2009. To appear in the selected papers of LICS 06. [ bib | pdf ] |
| [4] | T. Colcombet, “Regular cost functions over words (draft).” 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. [ bib | pdf ] |
2008
| [1] | M. Bojańczyk and T. Colcombet, “Tree-walking automata do not recognize all regular languages,” SIAM J. Comput., vol. 38, no. 2, pp. 658-701, 2008. [ bib ] |
| [2] | T. Colcombet and C. Löding, “The non-deterministic Mostowski hierarchy and distance-parity automata,” in ICALP 2008 (2): Automata, Languages and Programming, 35th International Colloquium (L. Aceto, I. Damgård, L. A. Goldberg, M. M. Halldórsson, A. Ingólfsdóttir, and I. Walukiewicz, eds.), vol. 5126 of Lecture Notes in Computer Science, pp. 398-409, Springer, 2008. [ bib | pdf ] |
| [3] | T. Colcombet and C. Löding, “The nesting-depth of disjunctive μ-calculus for tree languages and the limitedness problem,” in CSL 2008: Computer Science Logic, 22nd International Workshop (M. Kaminski and S. Martini, eds.), vol. 5213 of Lecture Notes in Computer Science, pp. 416-430, Springer, 2008. [ bib ] |
| [4] | A. Blumensath, T. Colcombet, and C. Löding, “Logical theories and compatible operations,” in Logic and Automata: History and Perspectives [in Honor of Wolfgang Thomas] (J. Flum, E. Grädel, and T. Wilke, eds.), vol. 2 of Texts in Logic and Games, pp. 73-106, Amsterdam University Press, 2008. [ bib ] |
2007
| [1] | T. Colcombet, “Factorisation forests for infinite words,” in FCT 2007: Fundamentals of Computation Theory, 16th International Symposium (E. Csuhaj-Varjú and Z. Ésik, eds.), vol. 4639 of Lecture Notes in Computer Science, pp. 226-237, Springer, 2007. [ bib | pdf ] |
| [2] | T. Colcombet, “A combinatorial theorem for trees: applications to monadic logic and infinite structures,” in ICALP 2007: Automata, Languages and Programming, 34th International Colloquium (L. Arge, C. Cachin, T. Jurdzinski, and A. Tarlecki, eds.), vol. 4596 of Lecture Notes in Computer Science, pp. 901-912, Springer, 2007. [ bib | pdf ] |
| [3] | T. Colcombet, “On Factorization Forests,” Tech. Rep. hal-00125047, Irisa Rennes, 2007. [ bib | pdf ] |
| [4] | T. Colcombet and C. Löding, “Transforming structures by set interpretations,” Logical Methods in Computer Science, vol. 3, no. 2, pp. 2:4, 36 pp. (electronic), 2007. [ bib | pdf ] |
2006
| [1] | M. Bojańczyk and T. Colcombet, “Tree-walking automata cannot be determinized,” Theoretical Computer Science, vol. 350, no. 2-3, pp. 164-173, 2006. [ bib | pdf ] |
| [2] | T. Colcombet and D. Niwiński, “On the positional determinacy of edge-labeled games,” Theoretical Computer Science, vol. 352, no. 1-3, pp. 190-196, 2006. [ bib | DOI | pdf ] |
| [3] | M. Bojańczyk and T. Colcombet, “Bounds in ω-regularity,” in LICS 06: 21th IEEE Symposium on Logic in Computer Science, pp. 285-296, 2006. [ bib | pdf ] |
| [4] | T. Colcombet and C. Löding, “Transforming structures by set interpretations,” Tech. Rep. AIB-2006-07, RWTH Aachen, 2006. [ bib | pdf ] |
2005
| [1] | M. Bojańczyk and T. Colcombet, “Tree-walking automata do not recognize all regular languages,” in STOC 2005: 37th Annual ACM Symposium on Theory of Computing, pp. 234-243, ACM, 2005. [ bib | pdf ] |
2004
| [1] | T. Colcombet, Propriétés et représentation de structures infinies (properties and representation of infinite structures). PhD thesis, Université Rennes I, Mar. 2004. [ bib | pdf ] |
| [2] | M. Bojańczyk and T. Colcombet, “Tree-walking automata cannot be determinized,” in ICALP 2004: Automata, Languages and Programming: 31st International Colloquium (J. Díaz, J. Karhumäki, A. Lepistö, and D. Sannella, eds.), vol. 3142 of Lecture Notes in Computer Science, pp. 246-256, Springer, 2004. [ bib | pdf ] |
| [3] | T. Colcombet and C. Löding, “On the expressiveness of deterministic transducers over infinite trees,” in STACS 2004: 21st International Symposium on Theoretical Aspects of Computer Science (V. Diekert and M. Habib, eds.), vol. 2996 of Lecture Notes in Computer Science, pp. 428-439, Springer, 2004. [ bib | pdf ] |
| [4] | T. Colcombet, “Equational presentations of tree-automatic structures,” in WASL 04, 2004. [ bib | pdf ] |
2003
| [1] | A. Carayol and T. Colcombet, “On equivalent representations of infinite structures,” in ICALP 2003: Automata, Languages and Programming, 30th International Colloquium (J. C. M. Baeten, J. K. Lenstra, J. Parrow, and G. J. Woeginger, eds.), vol. 2719 of Lecture Notes in Comput. Sci., pp. 599-610, Springer, 2003. [ bib | pdf ] |
2002
| [1] | T. Colcombet, “Rewriting in the partial algebra of typed terms modulo AC,” Electronic Notes in Theoretical Computer Science, vol. 68, no. 6, 2002. [ bib | pdf ] |
| [2] | T. Colcombet, “On families of graphs having a decidable first order theory with reachability,” in 29th ICALP, no. 2380 in Lecture Notes in Computer Science, (Malaga), pp. 98-109, Springer, 2002. [ bib | pdf ] |
2002
| [1] | T. Colcombet, “Rewriting in the partial algebra of typed terms modulo AC,” Electronic Notes in Theoretical Computer Science, vol. 68, no. 6, 2002. [ bib | pdf ] |
| [2] | T. Colcombet, “On families of graphs having a decidable first order theory with reachability,” in 29th ICALP, no. 2380 in Lecture Notes in Computer Science, (Malaga), pp. 98-109, Springer, 2002. [ bib | pdf ] |
2000
| [1] | T. Colcombet and P. Fradet, “Enforcing trace properties by program transformation,” in POPL 00: Proceedings of the 27th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (M. N. Wegman and T. W. Reps, eds.), pp. 54-66, ACM, 2000. [ bib | pdf ] |