Thomas Colcombet

According to our database, Thomas Colcombet authored at least 76 papers between 2000 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of four.

2024

From Muller to Parity and Rabin Automata: Optimal Transformations Preserving (History) Determinism.

Antonio Casares, Thomas Colcombet, Nathanaël Fijalkow, Karoliina Lehtinen

TheoretiCS, 2024

Playing Safe, Ten Years Later.

Thomas Colcombet, Nathanaël Fijalkow, Florian Horn

Log. Methods Comput. Sci., 2024

Tree algebras and bisimulation-invariant MSO on finite graphs.

Thomas Colcombet, Amina Doumane, Denis Kuperberg

CoRR, 2024

2023

ℤ-polyregular functions.

Thomas Colcombet, Gaëtan Douéneau-Tabot, Aliaume Lopez

Proceedings of the 38th Annual ACM/IEEE Symposium on Logic in Computer Science, 2023

2022

The Theory of Universal Graphs for Infinite Duration Games.

Thomas Colcombet, Nathanaël Fijalkow, Pawel Gawrychowski, Pierre Ohlmann

Log. Methods Comput. Sci., 2022

Cost Automata, Safe Schemes, and Downward Closures.

David Barozzini, Lorenzo Clemente, Thomas Colcombet, Pawel Parys

Fundam. Informaticae, 2022

A Complexity Approach to Tree Algebras: the Polynomial Case.

Thomas Colcombet, Arthur Jaquard

Proceedings of the 47th International Symposium on Mathematical Foundations of Computer Science, 2022

On the Size of Good-For-Games Rabin Automata and Its Link with the Memory in Muller Games.

Antonio Casares, Thomas Colcombet, Karoliina Lehtinen

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

First-order separation over countable ordinals.

Thomas Colcombet, Sam van Gool, Rémi Morvan

Proceedings of the Foundations of Software Science and Computation Structures, 2022

2021

Controlling a random population.

Thomas Colcombet, Nathanaël Fijalkow, Pierre Ohlmann

Log. Methods Comput. Sci., 2021

Unambiguity in Automata Theory (Dagstuhl Seminar 21452).

Thomas Colcombet, Karin Quaas, Michal Skrzypczak

Dagstuhl Reports, 2021

A Complexity Approach to Tree Algebras: the Bounded Case.

Thomas Colcombet, Arthur Jaquard

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

Optimal Transformations of Games and Automata Using Muller Conditions.

Antonio Casares, Thomas Colcombet, Nathanaël Fijalkow

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

Learning Automata and Transducers: A Categorical Approach.

Thomas Colcombet, Daniela Petrisan, Riccardo Stabile

Proceedings of the 29th EACSL Annual Conference on Computer Science Logic, 2021

The factorisation forest theorem.

Thomas Colcombet

Proceedings of the Handbook of Automata Theory., 2021

2020

Automata Minimization: a Functorial Approach.

Thomas Colcombet, Daniela Petrisan

Log. Methods Comput. Sci., 2020

Optimal transformations of Muller conditions.

Antonio Casares, Thomas Colcombet, Nathanaël Fijalkow

CoRR, 2020

Unambiguous Separators for Tropical Tree Automata.

Thomas Colcombet, Sylvain Lombardy

Proceedings of the 37th International Symposium on Theoretical Aspects of Computer Science, 2020

2019

On Reachability Problems for Low-Dimensional Matrix Semigroups.

Thomas Colcombet, Joël Ouaknine, Pavel Semukhin, James Worrell

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

Universal Graphs and Good for Games Automata: New Tools for Infinite Duration Games.

Thomas Colcombet, Nathanaël Fijalkow

Proceedings of the Foundations of Software Science and Computation Structures, 2019

2018

An Algebraic Approach to MSO-Definability on Countable linear Orderings.

Olivier Carton, Thomas Colcombet, Gabriele Puppis

J. Symb. Log., 2018

Parity games and universal graphs.

Thomas Colcombet, Nathanaël Fijalkow

CoRR, 2018

2017

Automata and minimization.

Thomas Colcombet, Daniela Petrisan

ACM SIGLOG News, 2017

Boundedness in languages of infinite words.

Mikolaj Bojanczyk, Thomas Colcombet

Log. Methods Comput. Sci., 2017

Automata in the Category of Glued Vector Spaces.

Thomas Colcombet, Daniela Petrisan

Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science, 2017

Perfect half space games.

Thomas Colcombet, Marcin Jurdzinski, Ranko Lazic, Sylvain Schmitz

Proceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, 2017

Logic and regular cost functions.

Thomas Colcombet

Proceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, 2017

Automata and Program Analysis.

Thomas Colcombet, Laure Daviaud, Florian Zuleger

Proceedings of the Fundamentals of Computation Theory - 21st International Symposium, 2017

2016

Approximate Comparison of Functions Computed by Distance Automata.

Thomas Colcombet, Laure Daviaud

Theory Comput. Syst., 2016

Cost Functions Definable by Min/Max Automata.

Thomas Colcombet, Denis Kuperberg, Amaldev Manuel, Szymon Torunczyk

Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science, 2016

On a Fragment of AMSO and Tiling Systems.

Achim Blumensath, Thomas Colcombet, Pawel Parys

Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science, 2016

Games with bound guess actions.

Thomas Colcombet, Stefan Göller

Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, 2016

The Bridge Between Regular Cost Functions and Omega-Regular Languages.

Thomas Colcombet, Nathanaël Fijalkow

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

2015

Logics with rigidly guarded data tests.

Thomas Colcombet, Clemens Ley, Gabriele Puppis

Log. Methods Comput. Sci., 2015

Combinatorial Expressions and Lower Bounds.

Thomas Colcombet, Amaldev Manuel

Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science, 2015

The Complexity of Boundedness for Guarded Logics.

Michael Benedikt, Balder ten Cate, Thomas Colcombet, Michael Vanden Boom

Proceedings of the 30th Annual ACM/IEEE Symposium on Logic in Computer Science, 2015

Limited Set quantifiers over Countable Linear Orderings.

Thomas Colcombet, A. V. Sreejith

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

Fragments of Fixpoint Logic on Data Words.

Thomas Colcombet, Amaldev Manuel

Proceedings of the 35th IARCS Annual Conference on Foundation of Software Technology and Theoretical Computer Science, 2015

Unambiguity in Automata Theory.

Thomas Colcombet

Proceedings of the Descriptional Complexity of Formal Systems, 2015

2014

$μ$-calculus on data words.

Thomas Colcombet, Amaldev Manuel

CoRR, 2014

Size-Change Abstraction and Max-Plus Automata.

Thomas Colcombet, Laure Daviaud, Florian Zuleger

Proceedings of the Mathematical Foundations of Computer Science 2014, 2014

Asymptotic Monadic Second-Order Logic.

Achim Blumensath, Olivier Carton, Thomas Colcombet

Proceedings of the Mathematical Foundations of Computer Science 2014, 2014

Generalized Data Automata and Fixpoint Logic.

Thomas Colcombet, Amaldev Manuel

Proceedings of the 34th International Conference on Foundation of Software Technology and Theoretical Computer Science, 2014

Playing Safe.

Thomas Colcombet, Nathanaël Fijalkow, Florian Horn

Proceedings of the 34th International Conference on Foundation of Software Technology and Theoretical Computer Science, 2014

Two-way cost automata and cost logics over infinite trees.

Achim Blumensath, Thomas Colcombet, Denis Kuperberg, Pawel Parys, Michael Vanden Boom

Proceedings of the Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), 2014

2013

Regular Cost Functions, Part I: Logic and Algebra over Words

Thomas Colcombet

Log. Methods Comput. Sci., 2013

Approximate comparison of distance automata.

Thomas Colcombet, Laure Daviaud

Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science, 2013

Magnitude Monadic Logic over Words and the Use of Relative Internal Set Theory.

Thomas Colcombet

Proceedings of the 28th Annual ACM/IEEE Symposium on Logic in Computer Science, 2013

Composition with Algebra at the Background - On a Question by Gurevich and Rabinovich on the Monadic Theory of Linear Orderings.

Thomas Colcombet

Proceedings of the Computer Science - Theory and Applications, 2013

Deciding the weak definability of Büchi definable tree languages.

Thomas Colcombet, Denis Kuperberg, Christof Löding, Michael Vanden Boom

Proceedings of the Computer Science Logic 2013 (CSL 2013), 2013

2012

Forms of Determinism for Automata (Invited Talk).

Thomas Colcombet

Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science, 2012

2011

On the Use of Guards for Logics with Data.

Thomas Colcombet, Clemens Ley, Gabriele Puppis

Proceedings of the Mathematical Foundations of Computer Science 2011, 2011

Green's Relations and Their Use in Automata Theory.

Thomas Colcombet

Proceedings of the Language and Automata Theory and Applications, 2011

Regular Languages of Words over Countable Linear Orderings.

Olivier Carton, Thomas Colcombet, Gabriele Puppis

Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

2010

Factorization forests for infinite words and applications to countable scattered linear orderings.

Thomas Colcombet

Theor. Comput. Sci., 2010

Regular Cost Functions over Finite Trees.

Thomas Colcombet, Christof Löding

Proceedings of the 25th Annual IEEE Symposium on Logic in Computer Science, 2010

Regular Temporal Cost Functions.

Thomas Colcombet, Denis Kuperberg, Sylvain Lombardy

Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

2009

A Tight Lower Bound for Determinization of Transition Labeled Büchi Automata.

Thomas Colcombet, Konrad Zdanowski

Proceedings of the Automata, Languages and Programming, 36th Internatilonal Colloquium, 2009

The Theory of Stabilisation Monoids and Regular Cost Functions.

Thomas Colcombet

Proceedings of the Automata, Languages and Programming, 36th Internatilonal Colloquium, 2009

2008

Tree-Walking Automata Do Not Recognize All Regular Languages.

Mikolaj Bojanczyk, Thomas Colcombet

SIAM J. Comput., 2008

The Non-deterministic Mostowski Hierarchy and Distance-Parity Automata.

Thomas Colcombet, Christof Löding

Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

The Nesting-Depth of Disjunctive µ-Calculus for Tree Languages and the Limitedness Problem.

Thomas Colcombet, Christof Löding

Proceedings of the Computer Science Logic, 22nd International Workshop, 2008

Logical theories and compatible operations.

Achim Blumensath, Thomas Colcombet, Christof Löding

Proceedings of the Logic and Automata: History and Perspectives [in Honor of Wolfgang Thomas]., 2008

2007

Transforming structures by set interpretations.

Thomas Colcombet, Christof Löding

Log. Methods Comput. Sci., 2007

On factorisation forests

Thomas Colcombet

CoRR, 2007

A Combinatorial Theorem for Trees.

Thomas Colcombet

Proceedings of the Automata, Languages and Programming, 34th International Colloquium, 2007

Factorisation Forests for Infinite Words.

Thomas Colcombet

Proceedings of the Fundamentals of Computation Theory, 16th International Symposium, 2007

2006

On the positional determinacy of edge-labeled games.

Thomas Colcombet, Damian Niwinski

Theor. Comput. Sci., 2006

Tree-walking automata cannot be determinized.

Mikolaj Bojanczyk, Thomas Colcombet

Theor. Comput. Sci., 2006

Bounds in w-Regularity.

Mikolaj Bojanczyk, Thomas Colcombet

Proceedings of the 21th IEEE Symposium on Logic in Computer Science (LICS 2006), 2006

2004

Représentations et propriétés de structures infinies. (Representations and properties of infinite structures).

Thomas Colcombet

PhD thesis, 2004

On the Expressiveness of Deterministic Transducers over Infinite Trees.

Thomas Colcombet, Christof Löding

Proceedings of the STACS 2004, 2004

2003

On Equivalent Representations of Infinite Structures.

Arnaud Carayol, Thomas Colcombet

Proceedings of the Automata, Languages and Programming, 30th International Colloquium, 2003

2002

Rewriting in the partial algebra of typed terms modulo AC.

Thomas Colcombet

Proceedings of the 4th International Workshop on Verification of Infinite-State Systems (CONCUR 2002 Satellite Workshop), 2002

On Families of Graphs Having a Decidable First Order Theory with Reachability.

Thomas Colcombet

Proceedings of the Automata, Languages and Programming, 29th International Colloquium, 2002

2000

Enforcing Trace Properties by Program Transformation.

Thomas Colcombet, Pascal Fradet

Proceedings of the POPL 2000, 2000