Publications with abstracts

2012

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

Abstract: We survey in this paper some variants around the notion of determinism. We present unambiguous automata, strongly unambiguous automata, prophetic automata, guidable automata, and history-deterministic automata. We instantiate these various notions for finite words, infinite words, finite trees, infinite trees, data languages, and cost functions.

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

Abstract: This chapter is devoted to the presentation of the factorisation forest theorem, a deep result due to Simon, which provides advanced Ramsey-like arguments in the context of algebra, au- tomata, and logic. We present several proofs and several variants the result, as well as applications.

2011

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

Abstract: We develop an algebraic model suitable for recognizing languages of words indexed by countable linear orderings. We prove that this notion of recognizability is effectively equivalent to definability in monadic second-order (MSO) logic. This reproves in particular the decidability of MSO logic over the rationals with order. Our proof also implies the first known collapse result for MSO logic over countable linear orderings.

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

Abstract: The objective of this survey is to present the ideal theory of monoids, the so-called Green's relations, and to illustrate the usefulness of this tool for solving automata related questions. We use Green's relations for proving four classical results related to au- tomata theory: The result of Sch{\"u}tzenberger characterizing star-free lan- guages, the theorem of factorization forests of Simon, the characteri- zation of infinite words of decidable monadic theory due to Semenov, and the result of determinization of automata over infinite words of Mc- Naughton.

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

Abstract: The notion of orbit finite data monoid was recently introduced by Bojanczyk as an algebraic object for defining recognizable languages of data words. In this paper, following Buchi's approach, we introduce the new logic "rigidly guarded MSO" and show that the languages of data words definable in this logic are exactly the languages recognizable by orbit finite data monoids. We also establish, following this time the approach of Schutzenberger, McNaughton and Papert, that the first-order variant of this logic exactly defines the languages recognizable by aperiodic orbit finite data monoids.

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

Abstract: The theory of regular cost functions is a quantitative extension to the classical notion of regularity. A cost function associates to each input a non-negative integer value (or infinity), as opposed to languages which only associate to each input the two values `inside' and `outside'. This theory is a continuation of the work on distance automata and similar models. These models of automata have been successfully used for solving the star-height problem, the finite power property, the finite substitution problem, the relative inclusion star-height problem and the boundedness problem for monadic-second order logic over words. Our notion of regularity can be -- as in the classical theory of regular languages -- equivalently defined in terms of automata, expressions, algebraic recognisability, and by a variant of the monadic second-order logic. Those equivalences are strict extensions of the corresponding classical results. The present paper introduces the cost monadic logic, the quantitative extension to the notion of monadic second-order logic we use, and show that some problems of existence of bounds are decidable for this logic. This is achieved by introducing the corresponding algebraic formalism: stabilisation monoids.

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

Abstract: Regular cost functions have been introduced recently as an extension of the notion of regular languages with counting capabilities, which retains strong closure, equivalence, and decidability properties. Cost functions are functions ranging over `N or infinity', and considered modulo an equivalence which preserves the existence of bounds over each subset of the domain. A central result in the theory of regular cost functions over words is the duality theorem stating that the two dual forms of automata, namely B- and S- automata, are equivalent. The only known proof of this result relies on the translation into an equivalent algebraic formalism. In this paper, we describe direct translations from hierarchical B-automata to S-automata and from hierarchical S-automata to B-automata. We furthermore describe how to optimize the number of counters of the output automaton, and how to make them hierarchical. This construction is reminiscent of the famous construction of Safra for the determinization of automata over innite words.

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]

Abstract: The theorem of factorization forests of Imre Simon shows the existence of nested factorizations --- ` la Ramsey --- for finite words. This theorem has important applications in a semigroup theory, and beyond. We provide two improvements to the standard result. First we improve on all previously known bounds. Second, we extend it to `every linear ordering'. We use this last variant in a simplified proof of the translation of recognisable languages over countable scattered linear orderings to languages accepted by automata.

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

Abstract: Regular cost functions have been introduced recently as an extension to the notion of regular languages with counting capabilities, which retains strong closure, equivalence, and decidability properties. The specificity of cost functions is that exact values are not considered, but only estimated. In this paper, we study the strict subclass of regular temporal cost functions. In such cost functions, it is only allowed to count the number of occurrences of consecutive events. For this reason, this model intends to measure the length of intervals, i.e., a discrete notion of time. We provide various equivalent representations for functions in this class, using automata, and `clock based' reduction to regular language . We show that the conversions are much simpler to obtain, and much more efficient than in the general case of regular cost functions. Our second aim in this paper is to use temporal cost function as a test-case for exploring the algebraic nature of regular cost functions. Following the seminal ideas of Schutzenberger, this results in a decidable algebraic characterization of regular temporal cost functions inside the class of regular cost functions.

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

Abstract: We develop the theory of regular cost functions over finite trees: a quantitative extension to the notion of regular languages of trees: Cost functions map each input (tree) to a value in omega + 1, and are considered modulo an equivalence relation which forgets about specific values, but preserves boundedness of functions on all subsets of the domain. We introduce nondeterministic and alternating finite tree cost automata for describing cost functions. We show that all these forms of automata are effectively equivalent. We also provide decision procedures for them. Finally, follow- ing B{\"u}chi's seminal idea, we use cost automata for provid- ing decision procedures for cost monadic logic, a quantita- tive extension of monadic second order logic.

2009

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

Abstract: We define a new class of languages of Ï‰-words, strictly extending Ï‰-regular languages. One way to present this new class is by a type of regular expreWe define a new class of languages of Ï‰-words, strictly extending Ï‰-regular languages. One way to present this new class is by a type of regular expressions. The new ex- pressions are an extension of Ï‰-regular expressions where two new variants of the Kleene star Lâˆ— are added: LB and LS . These new exponents are used to say that parts of the input word have bounded size, and that parts of the input can have arbitrarily large sizes, respectively. For instance, the expression (aB b)Ï‰ represents the language of infinite words over the letters a, b where there is a common bound on the number of consecutive letters a. The expression (aS b)Ï‰ represents a similar language, but this time the distance between consecutive b's is required to tend toward the infinite. We develop a theory for these languages, with a focus on decidability and closure. u We define an equivalent automaton model, extending B Ìˆ chi automata. The main techni- cal result is a complementation lemma that works for languages where only one type of exponent---either LB or LS ---is used. We use the closure and decidability results to obtain partial decidability results for the logic MSOLB, a logic obtained by extending monadic second-order logic with new quantifiers that speak about the size of sets. ssions. The new expressions are an extension of Ï‰-regular expressions where two new variants of the Kleene star Lâˆ— are added: LB and LS . These new exponents are used to say that parts of the input word have bounded size, and that parts of the input can have arbitrarily large sizes, respectively. For instance, the expression (aB b)Ï‰ represents the language of infinite words over the letters a, b where there is a common bound on the number of consecutive letters a. The expression (a^S b)^omega represents a similar language, but this time the distance between consecutive b's is required to tend toward the infinite. We develop a theory for these languages, with a focus on decidability and closure. We define an equivalent automaton model, extending Buchi automata. The main techni- cal result is a complementation lemma that works for languages where only one type of exponent---either L^B or L^S ---is used. We use the closure and decidability results to obtain partial decidability results for the logic MSOLB, a logic obtained by extending monadic second-order logic with new quantifiers that speak about the size of sets.

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]

Abstract: We introduce the notion of regular cost functions: a quantitative extension to the standard theory of regular languages. We provide equivalent characterisations of this notion by means of automata (extending the nested distance desert automata of Kirsten), of history-deterministic automata (history-determinism is a weakening of the standard notion of determinism, that replaces it in this context), and a suitable notion of recognisability by stabilisation monoids. We also provide closure and decidability results.

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]

Abstract: In this paper we establish a lower bound hist(n) for the problem of translating a B Ìˆchi word automaton of size n into a deterministic Rabin word automaton when both the Buchi and the Rabin condition label transitions rather than states. This lower bound exactly matches the known upper bound to this problem. The function hist(n) is in Omega((1.64n)n ) and in o((1.65n)n). Our result entails a lower bound of hist(nâˆ’1) when the input Buchi automaton has its Buchi acceptance condition labeling states (as it is usual). Those lower bounds remain when the output deterministic Rabin automaton has its Rabin acceptance condition labeling states.

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]

Abstract: We introduce and develop the notion of regular cost functions: a quantitative extension to the standard theory of regular languages. This work is a continuation of the works on distance automata and similar models. These models of automata have been successfully used for solving the star-height problem, the finite power property, the finite substitution problem, the relative inclusion star-height problem or the boundedness problem for monadic-second order logic over words. Our notion of regularity can be -- as in the classical theory of regular languages -- equivalently defined in terms of automata, of algebraic recognisability, and by a variant of the monadic second-order logic. Those equivalences are strict extensions of the corresponding classical results. The decidability of the limitedness problem of distance automata, as well as all its known variants can be deduced from our results.

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]

Abstract: Tree-walking automata are a natural sequential model for recognizing tree languages. It is well known that every tree language recognized by a tree-walking automaton is regular. We show that the converse does not hold.

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]

Abstract: Given a Rabin tree-language and natural numbers i, j, the language is said to be i,j-feasible if it is accepted by a parity automaton using priorities i,i+1,...,j. The i,j-feasibility induces a hierarchy over the Rabin-tree languages called the Mostowski hierarchy. In this paper we prove that the problem of deciding if a language is i,j-feasible is reducible to the uniform universality problem for distanceparity automata. Distance-parity automata form a new model of automata extending both the nested distance desert automata introduced by Kirsten in his proof of decidability of the star-height problem, and parity automata over infinite trees. Distance-parity automata, instead of accepting a language, attach to each tree a cost in omega+1. The uniform universality problem consists in determining if this cost function is bounded by a finite value.

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]

Abstract: In this paper we lift the result of Hashiguchi of decidability of the restricted star-height problem for words to the level of finite trees. Formally, we show that it is decidable, given a regular tree language L and a natural number k whether L can be described by a disjunctive Î¼-calculus formula with at most k nesting of fixpoints. We show the same result for disjunctive Î¼-formulas allowing substitution. The latter result is equivalent to deciding if the language is definable by a regular expression with nesting depth at most k of Kleene-stars. The proof, following the approach of Kirsten in the word case, goes by reduction to the decidability of the limitedness problem for non-deterministic nested distance desert automata over trees. We solve this problem in the more general framework of alternating tree automata.

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]

Abstract: We survey operations on (possibly infinite) relational structures that are compatible with logical theories in the sense that, if we apply the operation to given structures then we can compute the theory of the resulting structure from the theories of the arguments (the logics under consideration for the result and the arguments might differ). Besides general compatibility results for these operations we also present several results on restricted classes of structures, and their use for obtaining classes of infinite structures with decidable theories.

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

Abstract: We consider a new kind of interpretation over relational structures: finite sets interpretations. Those interpretations are defined by weak monadic second-order (WMSO) formulas with free set variables. They transform a given structure into a structure with a domain consisting of finite sets of elements of the orignal structure. The definition of these interpretations directly implies that they send structures with a decidable WMSO theory to structures with a decidable first-order theory. In this paper, we investigate the expressive power of such interpretations applied to infinite deterministic trees. The results can be used in the study of automatic and tree-automatic structures.

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

Abstract: Following the idea developed by I. Simon in his theorem of Ramseyan factorisation forests, we develop a result of `deterministic factorisations'. This extra determinism property makes it usable on trees (finite or infinite). We apply our result for proving that, over trees, every monadic interpretation is equivalent to the composition of a first-order interpretation (with access to the ancestor relation) and a monadic marking. Using this remark, we give new characterisations for prefix-recognisable structures and for the Caucal hierarchy. Furthermore, we believe that this approach has other potential applications.

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

Abstract: The theorem of factorisation forests shows the existence of nested factorisations --- a la Ramsey --- for finite words. This theorem has important applications in semigroup theory, and beyond. We provide two improvements to the standard result. First we improve on all previously known bounds for the standard theorem. Second, we extend it to every `complete linear ordering'. We use this variant in a simplified proof of complementation of automata over words of countable scattered domain.

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

Abstract: The theorem of factorisation forests shows the existence of nested factorisations --- a la Ramsey --- for finite words. This theorem has important applications in semigroup theory, and beyond. The purpose of this paper is to illustrate the importance of this approach in the context of automata over infinite words and trees. We extend the theorem of factorisation forest in two directions: we show that it is still valid for any word indexed by a linear ordering; and we show that it admits a deterministic variant for words indexed by well-orderings. A byproduct of this work is also an improvement on the known bounds for the original result. We apply the first variant for giving a simplified proof of the closure under complementation of rational sets of words indexed by countable scattered linear orderings. We apply the second variant in the analysis of monadic second-order logic over trees, yielding new results on monadic interpretations over trees. Consequences of it are new caracterisations of prefix-recognizable structures and of the Caucal hierarchy

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]

Abstract: Tree-walking automata are a natural sequential model for recognizing languages of finite trees. Such automata walk around the tree and may decide in the end to accept it. It is shown that deterministic tree-walking automata are weaker than nondeterministic tree-walking automata.

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

Abstract: It is well known that games with the parity winning condition admit positional determinacy : the winner has always a positional (memoryless) strategy. This property continues to hold if edges rather than vertices are labeled. We show that in this latter case the converse is also true. That is, a winning condition over arbitrary set of colors admits positional determinacy in all games if and only if it can be reduced to a parity condition with some finite number of priorities.

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

Abstract: We consider an extension of omega-regular expressions where two new variants of the Kleene star L^* are added: L^B and L^S. These exponents act as the standard star, but restrict the number of iterations to be bounded (for L^B) or to tend toward infinity (for L^S). These expressions can define languages that are not omega-regular. We develop a theory for these languages. We study the decidability and closure questions. We also define an equivalent automaton model, extending B{\"u}chi automata. This culminates with a --- partial --- complementation result.

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]

Abstract: Tree-walking automata are a natural sequential model for recognizing tree languages. Every tree language recognized by a tree walking automaton is regular. In this paper, we present a tree language which is regular but not recognized by any (nondeterministic) tree-walking automaton. This settles a conjecture of Engelfriet, Hoogeboom and Van Best. Moreover, the separating tree language is definable already in first-order logic over a signature containing the left-son, right-son, and ancester relation.

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]