Thomas Colcombet

104 papers A* 21A 7B 14C 1Misc 1Journal 43Unranked 15
YearRankTypeTitle / Venue / Authors
2026 J jnl
Expregular functions.
CoRR
Thomas Colcombet, Nathan Lhote, Pierre Ohlmann
2025 B conf
Lambdas, Transducers and MSO (Invited Talk).
MFCS
Thomas Colcombet
2025 B conf
On the Expansion of Monadic Second-Order Logic with Cantor-Bendixson Rank and Order Type Predicates.
CSL
Thomas Colcombet, Alexander Rabinovich
2025 J jnl
Regular expressions over countable words.
CoRR
Thomas Colcombet, A. V. Sreejith
2025 A* conf
Tree Algebras and Bisimulation-Invariant MSO on Finite Graphs.
ICALP
Thomas Colcombet, Amina Doumane, Denis Kuperberg
2024 J jnl
From Muller to Parity and Rabin Automata: Optimal Transformations Preserving (History) Determinism.
TheoretiCS
Antonio Casares, Thomas Colcombet, Nathanaël Fijalkow, Karoliina Lehtinen
2024 J jnl
Playing Safe, Ten Years Later.
Log. Methods Comput. Sci.
Thomas Colcombet, Nathanaël Fijalkow, Florian Horn
2024 J jnl
Tree algebras and bisimulation-invariant MSO on finite graphs.
CoRR
Thomas Colcombet, Amina Doumane, Denis Kuperberg
2023 J jnl
From Muller to Parity and Rabin Automata: Optimal Transformations Preserving (History-)Determinism.
CoRR
Antonio Casares, Thomas Colcombet, Nathanaël Fijalkow, Karoliina Lehtinen
2023 A* conf
ℤ-polyregular functions.
LICS
Thomas Colcombet, Gaëtan Douéneau-Tabot, Aliaume Lopez
2022 B conf
A Complexity Approach to Tree Algebras: the Polynomial Case.
MFCS
Thomas Colcombet, Arthur Jaquard
2022 J jnl
Cost Automata, Safe Schemes, and Downward Closures.
Fundam. Informaticae
David Barozzini, Lorenzo Clemente, Thomas Colcombet, Pawel Parys
2022 B conf
First-order separation over countable ordinals.
FoSSaCS
Thomas Colcombet, Sam van Gool, Rémi Morvan
2022 J jnl
First-order separation over countable ordinals.
CoRR
Thomas Colcombet, Sam van Gool, Rémi Morvan
2022 A* conf
On the Size of Good-For-Games Rabin Automata and Its Link with the Memory in Muller Games.
ICALP
Antonio Casares, Thomas Colcombet, Karoliina Lehtinen
2022 J jnl
On the size of good-for-games Rabin automata and its link with the memory in Muller games.
CoRR
Antonio Casares, Thomas Colcombet, Karoliina Lehtinen
2022 J jnl
Playing Safe, Ten Years Later.
CoRR
Thomas Colcombet, Nathanaël Fijalkow, Florian Horn
2022 J jnl
The Theory of Universal Graphs for Infinite Duration Games.
Log. Methods Comput. Sci.
Thomas Colcombet, Nathanaël Fijalkow, Pawel Gawrychowski, Pierre Ohlmann
2022 J jnl
Z-polyregular functions.
CoRR
Thomas Colcombet, Gaëtan Douéneau-Tabot, Aliaume Lopez
2021 A* conf
A Complexity Approach to Tree Algebras: the Bounded Case.
ICALP
Thomas Colcombet, Arthur Jaquard
2021 J jnl
Controlling a random population.
Log. Methods Comput. Sci.
Thomas Colcombet, Nathanaël Fijalkow, Pierre Ohlmann
2021 B conf
Learning Automata and Transducers: A Categorical Approach.
CSL
Thomas Colcombet, Daniela Petrisan, Riccardo Stabile
2021 A* conf
Optimal Transformations of Games and Automata Using Muller Conditions.
ICALP
Antonio Casares, Thomas Colcombet, Nathanaël Fijalkow
2021 J jnl
The Theory of Universal Graphs for Infinite Duration Games.
CoRR
Thomas Colcombet, Nathanaël Fijalkow, Pawel Gawrychowski, Pierre Ohlmann
2021 — ch.
The factorisation forest theorem.
Handbook of Automata Theory (I.)
Thomas Colcombet
2021 J jnl
Unambiguity in Automata Theory (Dagstuhl Seminar 21452).
Dagstuhl Reports
Thomas Colcombet, Karin Quaas, Michal Skrzypczak
2020 J jnl
Automata Minimization: a Functorial Approach.
Log. Methods Comput. Sci.
Thomas Colcombet, Daniela Petrisan
2020 B conf
Controlling a Random Population.
FoSSaCS
Thomas Colcombet, Nathanaël Fijalkow, Pierre Ohlmann
2020 A* conf
Cost Automata, Safe Schemes, and Downward Closures.
ICALP
David Barozzini, Lorenzo Clemente, Thomas Colcombet, Pawel Parys
2020 J jnl
Cost Automata, Safe Schemes, and Downward Closures.
CoRR
David Barozzini, Lorenzo Clemente, Thomas Colcombet, Pawel Parys
2020 J jnl
Learning automata and transducers: a categorical approach.
CoRR
Thomas Colcombet, Daniela Petrisan, Riccardo Stabile
2020 J jnl
Optimal transformations of Muller conditions.
CoRR
Antonio Casares, Thomas Colcombet, Nathanaël Fijalkow
2020 A conf
Unambiguous Separators for Tropical Tree Automata.
STACS
Thomas Colcombet, Sylvain Lombardy
2019 J jnl
Controlling a random population.
CoRR
Thomas Colcombet, Nathanaël Fijalkow, Pierre Ohlmann
2019 A* conf
On Reachability Problems for Low-Dimensional Matrix Semigroups.
ICALP
Thomas Colcombet, Joël Ouaknine, Pavel Semukhin, James Worrell
2019 J jnl
On reachability problems for low dimensional matrix semigroups.
CoRR
Thomas Colcombet, Joël Ouaknine, Pavel Semukhin, James Worrell
2019 J jnl
Unambiguous separators for tropical tree automata.
CoRR
Thomas Colcombet, Sylvain Lombardy
2019 B conf
Universal Graphs and Good for Games Automata: New Tools for Infinite Duration Games.
FoSSaCS
Thomas Colcombet, Nathanaël Fijalkow
2018 J jnl
An Algebraic Approach to MSO-Definability on Countable linear Orderings.
J. Symb. Log.
Olivier Carton, Thomas Colcombet, Gabriele Puppis
2018 J jnl
Parity games and universal graphs.
CoRR
Thomas Colcombet, Nathanaël Fijalkow
2017 B conf
Automata Minimization: a Functorial Approach.
CALCO
Thomas Colcombet, Daniela Petrisan
2017 J jnl
Automata Minimization: a Functorial Approach.
CoRR
Thomas Colcombet, Daniela Petrisan
2017 J jnl
Automata Minimization: a Functorial Approach.
CoRR
Thomas Colcombet, Daniela Petrisan
2017 B conf
Automata and Program Analysis.
FCT
Thomas Colcombet, Laure Daviaud, Florian Zuleger
2017 J jnl
Automata and minimization.
ACM SIGLOG News
Thomas Colcombet, Daniela Petrisan
2017 B conf
Automata in the Category of Glued Vector Spaces.
MFCS
Thomas Colcombet, Daniela Petrisan
2017 J jnl
Automata in the Category of Glued Vector Spaces.
CoRR
Thomas Colcombet, Daniela Petrisan
2017 J jnl
Boundedness in languages of infinite words.
CoRR
Mikolaj Bojanczyk, Thomas Colcombet
2017 J jnl
Boundedness in languages of infinite words.
Log. Methods Comput. Sci.
Mikolaj Bojanczyk, Thomas Colcombet
2017 A* conf
Logic and regular cost functions.
LICS
Thomas Colcombet
2017 J jnl
Perfect Half Space Games.
CoRR
Thomas Colcombet, Marcin Jurdzinski, Ranko Lazic, Sylvain Schmitz
2017 A* conf
Perfect half space games.
LICS
Thomas Colcombet, Marcin Jurdzinski, Ranko Lazic, Sylvain Schmitz
2017 J jnl
Regular Languages of Words over Countable Linear Orderings.
CoRR
Olivier Carton, Thomas Colcombet, Gabriele Puppis
2016 J jnl
Approximate Comparison of Functions Computed by Distance Automata.
Theory Comput. Syst.
Thomas Colcombet, Laure Daviaud
2016 A conf
Cost Functions Definable by Min/Max Automata.
STACS
Thomas Colcombet, Denis Kuperberg, Amaldev Manuel, Szymon Torunczyk
2016 A* conf
Games with bound guess actions.
LICS
Thomas Colcombet, Stefan Göller
2016 A conf
On a Fragment of AMSO and Tiling Systems.
STACS
Achim Blumensath, Thomas Colcombet, Pawel Parys
2016 A* conf
The Bridge Between Regular Cost Functions and Omega-Regular Languages.
ICALP
Thomas Colcombet, Nathanaël Fijalkow
2015 A conf
Combinatorial Expressions and Lower Bounds.
STACS
Thomas Colcombet, Amaldev Manuel
2015 — conf
Fragments of Fixpoint Logic on Data Words.
FSTTCS
Thomas Colcombet, Amaldev Manuel
2015 — conf
Limited Set quantifiers over Countable Linear Orderings.
ICALP (2)
Thomas Colcombet, A. V. Sreejith
2015 J jnl
Logics with rigidly guarded data tests.
Log. Methods Comput. Sci.
Thomas Colcombet, Clemens Ley, Gabriele Puppis
2015 A* conf
The Complexity of Boundedness for Guarded Logics.
LICS
Michael Benedikt, Balder ten Cate, Thomas Colcombet, Michael Vanden Boom
2015 — conf
Unambiguity in Automata Theory.
DCFS
Thomas Colcombet
2014 J jnl
$μ$-calculus on data words.
CoRR
Thomas Colcombet, Amaldev Manuel
2014 — conf
Asymptotic Monadic Second-Order Logic.
MFCS (1)
Achim Blumensath, Olivier Carton, Thomas Colcombet
2014 — conf
Generalized Data Automata and Fixpoint Logic.
FSTTCS
Thomas Colcombet, Amaldev Manuel
2014 — conf
Playing Safe.
FSTTCS
Thomas Colcombet, Nathanaël Fijalkow, Florian Horn
2014 — conf
Size-Change Abstraction and Max-Plus Automata.
MFCS (1)
Thomas Colcombet, Laure Daviaud, Florian Zuleger
2014 — conf
Two-way cost automata and cost logics over infinite trees.
CSL-LICS
Achim Blumensath, Thomas Colcombet, Denis Kuperberg, Pawel Parys, Michael Vanden Boom
2013 A conf
Approximate comparison of distance automata.
STACS
Thomas Colcombet, Laure Daviaud
2013 Misc conf
Composition with Algebra at the Background - On a Question by Gurevich and Rabinovich on the Monadic Theory of Linear Orderings.
CSR
Thomas Colcombet
2013 B conf
Deciding the weak definability of Büchi definable tree languages.
CSL
Thomas Colcombet, Denis Kuperberg, Christof Löding, Michael Vanden Boom
2013 A* conf
Magnitude Monadic Logic over Words and the Use of Relative Internal Set Theory.
LICS
Thomas Colcombet
2013 J jnl
Regular Cost Functions, Part I: Logic and Algebra over Words
Log. Methods Comput. Sci.
Thomas Colcombet
2012 A conf
Forms of Determinism for Automata (Invited Talk).
STACS
Thomas Colcombet
2011 C conf
Green's Relations and Their Use in Automata Theory.
LATA
Thomas Colcombet
2011 B conf
On the Use of Guards for Logics with Data.
MFCS
Thomas Colcombet, Clemens Ley, Gabriele Puppis
2011 — conf
Regular Languages of Words over Countable Linear Orderings.
ICALP (2)
Olivier Carton, Thomas Colcombet, Gabriele Puppis
2010 J jnl
Factorization forests for infinite words and applications to countable scattered linear orderings.
Theor. Comput. Sci.
Thomas Colcombet
2010 A* conf
Regular Cost Functions over Finite Trees.
LICS
Thomas Colcombet, Christof Löding
2010 — conf
Regular Temporal Cost Functions.
ICALP (2)
Thomas Colcombet, Denis Kuperberg, Sylvain Lombardy
2009 — conf
A Tight Lower Bound for Determinization of Transition Labeled Büchi Automata.
ICALP (2)
Thomas Colcombet, Konrad Zdanowski
2009 — conf
The Theory of Stabilisation Monoids and Regular Cost Functions.
ICALP (2)
Thomas Colcombet
2008 — conf
Logical theories and compatible operations.
Logic and Automata
Achim Blumensath, Thomas Colcombet, Christof Löding
2008 B conf
The Nesting-Depth of Disjunctive µ-Calculus for Tree Languages and the Limitedness Problem.
CSL
Thomas Colcombet, Christof Löding
2008 — conf
The Non-deterministic Mostowski Hierarchy and Distance-Parity Automata.
ICALP (2)
Thomas Colcombet, Christof Löding
2008 J jnl
Tree-Walking Automata Do Not Recognize All Regular Languages.
SIAM J. Comput.
Mikolaj Bojanczyk, Thomas Colcombet
2007 A* conf
A Combinatorial Theorem for Trees.
ICALP
Thomas Colcombet
2007 B conf
Factorisation Forests for Infinite Words.
FCT
Thomas Colcombet
2007 J jnl
On factorisation forests
CoRR
Thomas Colcombet
2007 J jnl
Transforming structures by set interpretations
CoRR
Thomas Colcombet, Christof Löding
2007 J jnl
Transforming structures by set interpretations.
Log. Methods Comput. Sci.
Thomas Colcombet, Christof Löding
2006 A* conf
Bounds in w-Regularity.
LICS
Mikolaj Bojanczyk, Thomas Colcombet
2006 J jnl
On the positional determinacy of edge-labeled games.
Theor. Comput. Sci.
Thomas Colcombet, Damian Niwinski
2006 J jnl
Tree-walking automata cannot be determinized.
Theor. Comput. Sci.
Mikolaj Bojanczyk, Thomas Colcombet
2005 A* conf
Tree-walking automata do not recognize all regular languages.
STOC
Mikolaj Bojanczyk, Thomas Colcombet
2004 A conf
On the Expressiveness of Deterministic Transducers over Infinite Trees.
STACS
Thomas Colcombet, Christof Löding
2004 — —
Représentations et propriétés de structures infinies. (Representations and properties of infinite structures).
Thomas Colcombet
2004 A* conf
Tree-Walking Automata Cannot Be Determinized.
ICALP
Mikolaj Bojanczyk, Thomas Colcombet
2003 A* conf
On Equivalent Representations of Infinite Structures.
ICALP
Arnaud Carayol, Thomas Colcombet
2002 A* conf
On Families of Graphs Having a Decidable First Order Theory with Reachability.
ICALP
Thomas Colcombet
2002 — conf
Rewriting in the partial algebra of typed terms modulo AC.
INFINITY
Thomas Colcombet
2000 A* conf
Enforcing Trace Properties by Program Transformation.
POPL
Thomas Colcombet, Pascal Fradet