%% This BibTeX bibliography file was created using BibDesk.
%% http://bibdesk.sourceforge.net/
%% Created for Thomas Colcombet at 2012-01-09 16:07:49 +0100
%% Saved with string encoding Unicode (UTF-8)
@string{ap = {A para{\^{\i}}tre}}
@string{apd = {A para{\^{\i}}tre dans}}
@string{elsevier = {Elsevier}}
@string{entcs = {Electronic Notes in Theoretical Computer Science}}
@string{et = {et}}
@string{fct = {FCT}}
@string{lmcs = {Logical Methods in Computer Science}}
@string{lncs = {Lecture Notes in Computer Science}}
@string{popl = {POPL}}
@string{siamjc = {SIAM Journal on Computing}}
@string{soumis = {Soumis}}
@string{soumisa = {Soumis {\`a}}}
@string{springer = {Springer}}
@string{tcs = {Theoretical Computer Science}}
@string{tr = {Rapport interne}}
@string{trlitp = {Rapport {LITP}}}
@string{univp6 = {Universit\'e Paris~6 (France)}}
@string{univp7 = {Universit\'e Paris~7 (France)}}
@unpublished{colcombetHandbookFFT,
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.
},
Author = {Thomas Colcombet},
Date-Added = {2011-12-20 15:12:59 +0000},
Date-Modified = {2011-12-20 15:14:36 +0000},
Note = {To appear in the handbook ``Automata: from Mathematics to Applications''},
Title = {The Factorisation Forest Theorem},
Year = {2012},
Bdsk-File-1 = {YnBsaXN0MDDUAQIDBAUIJidUJHRvcFgkb2JqZWN0c1gkdmVyc2lvblkkYXJjaGl2ZXLRBgdUcm9vdIABqAkKFRYXGyIjVSRudWxs0wsMDQ4RFFpOUy5vYmplY3RzV05TLmtleXNWJGNsYXNzog8QgASABqISE4ACgAOAB1lhbGlhc0RhdGFccmVsYXRpdmVQYXRo0hgNGRpXTlMuZGF0YU8RAfwAAAAAAfwAAgAADE1hY2ludG9zaCBIRAAAAAAAAAAAAAAAAAAAAMo8jSNIKwAAAAn7KRBoYW5kYm9va19mZnQucGRmAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAGaE5yvk2OQAAAAAAAAAAAAMABAAACSAAAAAAAAAAAAAAAAAAAAAXQXV0b21hdGhhSGFuZGJvb2tSYW1zZXkAABAACAAAyjxxAwAAABEACAAAyvkoKQAAAAEAGAAJ+ykACfk+AAn4pwAJ+HQABQD+AAC/MQACAGZNYWNpbnRvc2ggSEQ6VXNlcnM6AHRob21hc2NvbGNvbWJldDoAQm91bG90OgBDdXJyZW50OgBQZXJzbzoAQXV0b21hdGhhSGFuZGJvb2tSYW1zZXk6AGhhbmRib29rX2ZmdC5wZGYADgAiABAAaABhAG4AZABiAG8AbwBrAF8AZgBmAHQALgBwAGQAZgAPABoADABNAGEAYwBpAG4AdABvAHMAaAAgAEgARAASAFNVc2Vycy90aG9tYXNjb2xjb21iZXQvQm91bG90L0N1cnJlbnQvUGVyc28vQXV0b21hdGhhSGFuZGJvb2tSYW1zZXkvaGFuZGJvb2tfZmZ0LnBkZgAAEwABLwAAFQACABb//wAAgAXSHB0eH1gkY2xhc3Nlc1okY2xhc3NuYW1lox8gIV1OU011dGFibGVEYXRhVk5TRGF0YVhOU09iamVjdF8QPy4uLy4uLy4uL0N1cnJlbnQvUGVyc28vQXV0b21hdGhhSGFuZGJvb2tSYW1zZXkvaGFuZGJvb2tfZmZ0LnBkZtIcHSQloiUhXE5TRGljdGlvbmFyeRIAAYagXxAPTlNLZXllZEFyY2hpdmVyAAgAEQAWAB8AKAAyADUAOgA8AEUASwBSAF0AZQBsAG8AcQBzAHYAeAB6AHwAhgCTAJgAoAKgAqICpwKwArsCvwLNAtQC3QMfAyQDJwM0AzkAAAAAAAACAQAAAAAAAAAoAAAAAAAAAAAAAAAAAAADSw==}}
@inproceedings{STACS12:colcombet,
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.},
Author = {Thomas Colcombet},
Booktitle = {STACS},
Date-Added = {2011-12-20 14:50:58 +0000},
Date-Modified = {2012-01-09 15:07:45 +0000},
Note = {To appear.},
Pdf = {Publications/STACS12-colcombet.pdf},
Title = {Forms of Determinism for Automata},
Year = {2012}}
@inproceedings{LATA11:colcombet,
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.},
Author = {Thomas Colcombet},
Booktitle = {LATA},
Date-Added = {2011-12-20 14:47:01 +0000},
Date-Modified = {2011-12-20 15:10:21 +0000},
Pages = {1-21},
Pdf = {Publications/LATA11-colcombet.pdf},
Title = {Green's Relations and Their Use in Automata Theory},
Year = {2011}}
@conference{POPL00:colcombet-fradet,
Address = {Boston},
Author = {Thomas Colcombet and Pascal Fradet},
Booktitle = {POPL 00},
Month = jan,
Pages = {54--66},
Pdf = {Publications/POPL00-colcombet-fradet.pdf},
Publisher = {ACM},
Title = {Enforcing Trace Properties by Program Transformation},
Year = 2000}
@conference{ICALP02:colcombet,
Address = {Malaga},
Author = {Thomas Colcombet},
Booktitle = {29th ICALP},
Month = jul,
Note = {Best student paper award, track B},
Number = {2380},
Pages = {98--109},
Pdf = {Publications/ICALP02-colcombet.pdf},
Publisher = {Springer},
Series = LNCS,
Title = {On Families of Graphs Having a Decidable First Order Theory with Reachability},
Year = {2002}}
@article{ENTCS02:colcombet,
Author = {Thomas Colcombet},
Editor = {Antonin Kucera and Richard Mayr},
Journal = ENTCS,
Number = 6,
Pdf = {Publications/ENTCS02-colcombet.pdf},
Publisher = ELSEVIER,
Title = {Rewriting in the partial algebra of typed terms modulo {AC}},
Volume = {68},
Year = {2002}}
@conference{ICALP03:carayol-colcombet,
Address = Eindhoven,
Author = {Arnaud Carayol and Thomas Colcombet},
Booktitle = {30th ICALP},
Month = jul,
Number = 2719,
Pdf = {Publications/ICALP03-carayol-colcombet.pdf},
Publisher = SPRINGER,
Series = LNCS,
Title = {On Equivalent Representations of Infinite Structures},
Year = 2003}
@conference{STACS04:colcombet-loeding,
Address = Montpellier,
Author = {Colcombet, Thomas and Christof L\"oding},
Booktitle = {STACS 04},
Month = mar,
Number = 2996,
Pages = {428--439},
Pdf = {Publications/STACS04-colcombet-loeding.pdf},
Publisher = SPRINGER,
Series = LNCS,
Title = {On the Expressiveness of Deterministic Transducers over Infinite Trees},
Year = 2004}
@conference{ICALP04:bojanczyc-colcombet,
Address = {Turku},
Author = {Mikolaj Boja\'nczyk and Thomas Colcombet},
Booktitle = {31th ICALP},
Date-Modified = {2011-12-21 23:05:15 +0000},
Note = {Best paper award, track B},
Number = 3142,
Pages = {246--256},
Pdf = {Publications/ICALP04-bojanczyc-colcombet.pdf},
Publisher = SPRINGER,
Series = LNCS,
Title = {Tree-Walking Automata Cannot Be Determinized},
Year = 2004}
@phdthesis{PHD04:colcombet,
Author = {Thomas Colcombet},
Month = mar,
Pdf = {Publications/PHD04-colcombet.pdf},
School = {Universit\'e Rennes I},
Title = {Propri{\'e}t\'es et repr\'esentation de structures infinies (properties and representation of infinite structures)},
Year = 2004}
@conference{WASL04:colcombet,
Address = Auckland,
Author = {Thomas Colcombet},
Booktitle = {WASL 04},
Date-Modified = {2011-12-21 23:05:10 +0000},
Pdf = {Publications/WASL04-colcombet.pdf},
Title = {Equational presentations of tree-automatic structures},
Year = 2004}
@conference{STOC05:bojanczyk-colcombet,
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.},
Address = {Baltimore},
Author = {Mikolaj Boja\'nczyk and Thomas Colcombet},
Booktitle = {STOC 05},
Date-Modified = {2011-12-21 23:05:05 +0000},
Pages = {234--243},
Pdf = {Publications/STOC05-bojanczyk-colcombet.pdf},
Title = {Tree-Walking Automata Do Not Recognize All Regular Languages},
Year = 2005}
@article{TCS06:colcombet-niwinski,
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.},
Author = {Thomas Colcombet and Damian Niwi\'nski},
Journal = TCS,
Number = {1-3},
Pages = {190--196},
Pdf = {Publications/TCS06-colcombet-niwinski.pdf},
Title = {On the positional determinacy of edge-labeled games},
Volume = {352},
Year = {2006}}
@article{TCS06:bojanczyk-colcombet,
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.},
Author = {Mikolaj Boja\'nczyk and Thomas Colcombet},
Journal = TCS,
Note = {Selected papers of ICALP 04},
Number = {2-3},
Pages = {164--173},
Pdf = {Publications/TCS06-bojanczyk-colcombet.pdf},
Title = {Tree-walking automata cannot be determinized},
Volume = {350},
Year = {2006}}
@techreport{RR06:colcombet-loeding,
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.},
Author = {Thomas Colcombet and Christof L{\"o}ding},
Date-Modified = {2011-12-21 23:05:17 +0000},
Institution = {RWTH Aachen},
Number = {AIB-2006-07},
Pdf = {Publications/RR06-colcombet-loeding.pdf},
Title = {Transforming structures by set interpretations},
Year = {2006}}
@conference{LICS06:bojanczyk-colcombet,
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.},
Author = {Mikolaj Boja\'nczyk and Thomas Colcombet},
Booktitle = {LICS 06},
Date-Modified = {2011-12-21 23:05:17 +0000},
Pages = {285-296},
Pdf = {Publications/LICS06-bojanczyk-colcombet.pdf},
Title = {Bounds in $\omega$-regularity},
Year = 2006}
@techreport{HAL07:colcombet-factorisations,
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},
Author = {Thomas Colcombet},
Institution = {{Irisa Rennes}},
Number = {{hal-00125047}},
Pdf = {Publications/HAL07-colcombet.pdf},
Title = {{On Factorization Forests}},
Year = 2007}
@conference{ICALP07:colcombet-factorisations,
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.},
Address = {Wroc{\l}aw},
Author = {Thomas Colcombet},
Booktitle = {34th ICALP},
Date-Modified = {2011-12-21 23:04:42 +0000},
Number = 4596,
Pages = {901--912},
Pdf = {Publications/ICALP07-colcombet.pdf},
Publisher = SPRINGER,
Series = LNCS,
Title = {A combinatorial theorem for trees},
Year = 2007}
@conference{FCT07:colcombet-factorisations-scat,
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.},
Address = {Budapest},
Author = {Thomas Colcombet},
Booktitle = {FCT 07},
Date-Modified = {2011-12-21 23:05:17 +0000},
Number = 4639,
Pages = {226--237},
Pdf = {Publications/FCT07-colcombet.pdf},
Publisher = SPRINGER,
Series = LNCS,
Title = {Factorisation forests for infinite words},
Year = {2007}}
@article{LMCS07:colcombet-loeding-set-interpretations,
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.},
Author = {Thomas Colcombet and Christof L{\"o}ding},
Journal = LMCS,
Number = {4},
Pdf = {Publications/LMCS07-colcombet-loeding.pdf},
Title = {Transforming structures by set interpretations},
Volume = {3-2},
Year = {2007}}
@inbook{AGHP07:blumensath-colcombet-loeding-compatible,
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.},
Author = {Achim Blumensath and Thomas Colcombet and Christof L\"oding},
Editors = {Erich Gr{\"a}del and J\"org Flum and Thomas Wilke},
Journal = {Logic and Automata: History and Perspectives},
Pages = {75--109},
Pdf = {Publications/60th07-blumensath-colcombet-loeding.pdf},
Publisher = {Amsterdam University Press},
Title = {Logical Theories and Compatible Operations},
Volume = {Text in Logics and Games 2},
Year = {2007}}
@article{SIAM08:bojanczyk-colcombet-twa,
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.},
Author = {Mikolaj Boja\'nczyk and Thomas Colcombet},
Doi = {10.1137/050645427},
Journal = SIAMjc,
Note = {Selected papers of STOC 05},
Number = {2},
Pages = {658--701},
Publisher = {SIAM},
Title = {Tree-Walking Automata Do Not Recognize All Regular Languages},
Volume = {38},
Year = 2008,
Bdsk-Url-1 = {http://dx.doi.org/10.1137/050645427}}
@conference{ICALP08:colcombet-loeding-mostowski,
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.},
Address = {Reykjavik},
Author = {Thomas Colcombet and Christof L\"oding},
Booktitle = {35th ICALP},
Date-Modified = {2011-12-21 23:04:22 +0000},
Number = 5126,
Pages = {398--409},
Pdf = {Publications/ICALP08-colcombet-loeding.pdf},
Publisher = SPRINGER,
Series = LNCS,
Title = {The non-deterministic Mostowski hierarchy and distance-parity automata},
Year = 2008}
@conference{CSL08:colcombet-loeding-depth-mu-calculus,
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.
},
Address = {Bertinoro},
Author = {Thomas Colcombet and Christof {\"o}ding},
Booktitle = {CSL},
Date-Modified = {2011-12-21 23:04:42 +0000},
Number = 5213,
Pages = {416--430},
Pdf = {Publications/CSL08-colcombet-loeding.pdf},
Publisher = SPRINGER,
Series = LNCS,
Title = {The Nesting-Depth of Disjunctive $\mu$-calculus for Tree Languages and the Limitedness Problem},
Year = 2008}
@article{LMCS09:bojanczyk-colcombet-lics,
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.
},
Author = {Mikolaj Boja\'nczyk and Thomas Colcombet},
Journal = LMCS,
Note = {To appear in the selected papers of LICS 06},
Pdf = {Publications/LMCS-bojanczyk-colcombet-to-appear.pdf},
Title = {Bounds in $\omega$-regularity},
Year = 2009}
@conference{ICALP09:colcombet-cost-function,
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.
},
Address = {Rhodos},
Author = {Thomas Colcombet},
Booktitle = {36th ICALP},
Month = jul,
Number = 5556,
Pages = {139--150},
Pdf = {Publications/ICALP09-colcombet.pdf},
Publisher = SPRINGER,
Series = LNCS,
Title = {The Theory of Stabilisation Monoids and Regular Cost Functions},
Year = 2009}
@conference{ICALP09:colcombet-zdanowski-determinization,
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.
},
Address = {Rhodos},
Author = {Thomas Colcombet and Konrad Zdanowski},
Booktitle = {36th ICALP},
Month = jul,
Number = 5556,
Pages = {151--162},
Pdf = {Publications/ICALP09-colcombet-zdanowski.pdf},
Publisher = SPRINGER,
Series = LNCS,
Title = {A Tight Lower Bound for Determinization of Transition Labeled B{\"u}chi Automata},
Year = 2009}
@article{TCS10:colcombet-fct,
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.
},
Author = {Thomas Colcombet},
Issue = {4-5},
Journal = TCS,
Note = {Selected papers of FCT 07},
Pages = {751--764},
Pdf = {Publications/TCS10-colcombet.pdf},
Title = {Factorisation Forests for Infinite Words and applications to countable scattered linear orderings},
Volume = 411,
Year = {2010}}
@conference{ICALP10:colcombet-kuperberg-lombardy,
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.
},
Author = {Thomas Colcombet and Denis Kuperberg and Sylvain Lombardy},
Booktitle = {ICALP (2)},
Pages = {563-574},
Pdf = {Publications/ICALP10-colcombet-kuperberg-lombardy-submitted.pdf},
Title = {Regular Temporal Cost Functions},
Year = {2010}}
@conference{LICS10:colcombet-loeding,
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.
},
Author = {Thomas Colcombet and Christof L\"oding},
Booktitle = {LICS},
Pages = {70-79},
Pdf = {Publications/LICS10-colcombet-loeding-submitted.pdf},
Title = {Regular cost functions over finite trees},
Year = {2010}}
@unpublished{LMCS_stabilisation_monoid_10,
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.},
Author = {Thomas Colcombet},
Date-Modified = {2011-11-22 09:20:46 +0000},
Note = {Submitted, Special issue of ICALP09},
Pdf = {Publications/LMCS_stabilisation_monoids_v2_submitted.pdf},
Title = {Regular cost functions, Part~{I}: logic and algebra over words},
Year = 2011}
@unpublished{regular-cost-functions-working09,
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.
},
Author = {Thomas Colcombet},
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'},
Pdf = {Publications/unpublished09-colcombet-cost-function.pdf},
Title = {Regular cost functions over words (draft)},
Year = 2009}
@inproceedings{MFCS11:ColcombetLeyPuppis,
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.
},
Author = {Thomas Colcombet and Clemens Ley and Gabriele Puppis},
Booktitle = {MFCS},
Ee = {http://dx.doi.org/10.1007/978-3-642-22993-0_24},
Pages = {243-255},
Pdf = {Publications/MFCS11-colcombet-ley-puppis.pdf},
Title = {On the Use of Guards for Logics with Data},
Year = {2011}}
@inproceedings{ICALP11:Carton-Colcombet-Puppis,
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.
},
Author = {Olivier Carton and Thomas Colcombet and Gabriele Puppis},
Booktitle = {ICALP (2)},
Ee = {http://dx.doi.org/10.1007/978-3-642-22012-8_9},
Pages = {125-136},
Pdf = {Publications/ICALP11-carton-colcombet-puppis.pdf},
Title = {Regular Languages of Words over Countable Linear Orderings},
Year = {2011}}
@unpublished{safra-like-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.
},
Author = {Thomas Colcombet},
Date-Modified = {2011-12-20 15:15:41 +0000},
Note = {Unpublished},
Title = {Safra-like constructions for regular cost functions over finite words},
Year = 2011}
