%% This BibTeX bibliography file was created using BibDesk.
%% http://bibdesk.sourceforge.net/
%% Created for Thomas Colcombet at 2013-04-22 15:51:54 +0200
%% 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)}}
@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 = {Boja{\'n}czyk, Miko{\l}aj and Colcombet, Thomas},
Date-Added = {2013-04-22 12:59:39 +0000},
Date-Modified = {2013-04-22 13:16:34 +0000},
Fjournal = {SIAM Journal on Computing},
Journal = {SIAM J. Comput.},
Number = {2},
Pages = {658--701},
Title = {Tree-walking automata do not recognize all regular languages},
Volume = {38},
Year = {2008},
Bdsk-File-1 = {YnBsaXN0MDDUAQIDBAUGJCVYJHZlcnNpb25YJG9iamVjdHNZJGFyY2hpdmVyVCR0b3ASAAGGoKgHCBMUFRYaIVUkbnVsbNMJCgsMDRBWJGNsYXNzV05TLmtleXNaTlMub2JqZWN0c4AHog4PgAKAA6IREoAEgAVccmVsYXRpdmVQYXRoWWFsaWFzRGF0YV8QOS4uLy4uLy4uL01lbW9zL1BhcGllcnMvU0lBTTA4LXR3YS1ib2phbmN6eWstY29sY29tYmV0LnBkZtIJFxgZV05TLmRhdGGABk8RAfwAAAAAAfwAAgAADE1hY2ludG9zaCBIRAAAAAAAAAAAAAAAAAAAAMo8jSNIKwAAAAn5Kh9TSUFNMDgtdHdhLWJvamFuY3p5ayMxREVCQzIucGRmAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAHevCyydFpgAAAAAAAAAAAAMAAwAACSAAAAAAAAAAAAAAAAAAAAAHUGFwaWVycwAAEAAIAADKPHEDAAAAEQAIAADLJzeWAAAAAQAUAAn5KgAJ+KkACfh0AAUA/gAAvzEAAgBcTWFjaW50b3NoIEhEOlVzZXJzOgB0aG9tYXNjb2xjb21iZXQ6AEJvdWxvdDoATWVtb3M6AFBhcGllcnM6AFNJQU0wOC10d2EtYm9qYW5jenlrIzFERUJDMi5wZGYADgBGACIAUwBJAEEATQAwADgALQB0AHcAYQAtAGIAbwBqAGEAbgBjAHoAeQBrAC0AYwBvAGwAYwBvAG0AYgBlAHQALgBwAGQAZgAPABoADABNAGEAYwBpAG4AdABvAHMAaAAgAEgARAASAE1Vc2Vycy90aG9tYXNjb2xjb21iZXQvQm91bG90L01lbW9zL1BhcGllcnMvU0lBTTA4LXR3YS1ib2phbmN6eWstY29sY29tYmV0LnBkZgAAEwABLwAAFQACABb//wAA0hscHR5aJGNsYXNzbmFtZVgkY2xhc3Nlc11OU011dGFibGVEYXRhox0fIFZOU0RhdGFYTlNPYmplY3TSGxwiI1xOU0RpY3Rpb25hcnmiIiBfEA9OU0tleWVkQXJjaGl2ZXLRJidUcm9vdIABAAgAEQAaACMALQAyADcAQABGAE0AVABcAGcAaQBsAG4AcABzAHUAdwCEAI4AygDPANcA2QLZAt4C6QLyAwADBAMLAxQDGQMmAykDOwM+A0MAAAAAAAACAQAAAAAAAAAoAAAAAAAAAAAAAAAAAAADRQ==},
Bdsk-Url-1 = {http://dx.doi.org/10.1137/050645427}}
@inproceedings{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 ancestor relations.},
Author = {Boja{\'n}czyk, Miko{\l}aj and Colcombet, Thomas},
Booktitle = {STOC 2005: 37th {A}nnual {ACM} {S}ymposium on {T}heory of {C}omputing},
Date-Added = {2013-04-22 12:59:39 +0000},
Date-Modified = {2013-04-22 13:45:05 +0000},
Pages = {234--243},
Pdf = {Publications/STOC05-bojanczyk-colcombet.pdf},
Publisher = {ACM},
Title = {Tree-walking automata do not recognize all regular languages},
Year = {2005},
Bdsk-File-1 = {YnBsaXN0MDDUAQIDBAUGJCVYJHZlcnNpb25YJG9iamVjdHNZJGFyY2hpdmVyVCR0b3ASAAGGoKgHCBMUFRYaIVUkbnVsbNMJCgsMDRBWJGNsYXNzV05TLmtleXNaTlMub2JqZWN0c4AHog4PgAKAA6IREoAEgAVccmVsYXRpdmVQYXRoWWFsaWFzRGF0YV8QLi4uL1B1YmxpY2F0aW9ucy9TVE9DMDUtYm9qYW5jenlrLWNvbGNvbWJldC5wZGbSCRcYGVdOUy5kYXRhgAZPEQIWAAAAAAIWAAIAAAxNYWNpbnRvc2ggSEQAAAAAAAAAAAAAAAAAAADKPI0jSCsAAAAJ+4YeU1RPQzA1LWJvamFuY3p5ay1jb2xjb21iZXQucGRmAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAoElcqrXkoAAAAAAAAAAAABAAIAAAkgAAAAAAAAAAAAAAAAAAAADFB1YmxpY2F0aW9ucwAQAAgAAMo8cQMAAAARAAgAAMqrQioAAAABABgACfuGAAn5YwAJ+LYACfh0AAUA/gAAvzEAAgBrTWFjaW50b3NoIEhEOlVzZXJzOgB0aG9tYXNjb2xjb21iZXQ6AEJvdWxvdDoAV2ViOgBwdWJsaWNfaHRtbDoAUHVibGljYXRpb25zOgBTVE9DMDUtYm9qYW5jenlrLWNvbGNvbWJldC5wZGYAAA4APgAeAFMAVABPAEMAMAA1AC0AYgBvAGoAYQBuAGMAegB5AGsALQBjAG8AbABjAG8AbQBiAGUAdAAuAHAAZABmAA8AGgAMAE0AYQBjAGkAbgB0AG8AcwBoACAASABEABIAWFVzZXJzL3Rob21hc2NvbGNvbWJldC9Cb3Vsb3QvV2ViL3B1YmxpY19odG1sL1B1YmxpY2F0aW9ucy9TVE9DMDUtYm9qYW5jenlrLWNvbGNvbWJldC5wZGYAEwABLwAAFQACABb//wAA0hscHR5aJGNsYXNzbmFtZVgkY2xhc3Nlc11OU011dGFibGVEYXRhox0fIFZOU0RhdGFYTlNPYmplY3TSGxwiI1xOU0RpY3Rpb25hcnmiIiBfEA9OU0tleWVkQXJjaGl2ZXLRJidUcm9vdIABAAgAEQAaACMALQAyADcAQABGAE0AVABcAGcAaQBsAG4AcABzAHUAdwCEAI4AvwDEAMwAzgLoAu0C+AMBAw8DEwMaAyMDKAM1AzgDSgNNA1IAAAAAAAACAQAAAAAAAAAoAAAAAAAAAAAAAAAAAAADVA==},
Bdsk-Url-1 = {http://dx.doi.org/10.1145/1060590.1060626}}
@inproceedings{ICALP04:bojanczyc-colcombet,
Abstract = {Tree-walking automata are a natural sequential model for recognizing tree languages. It is shown that deterministic tree-walking automata are weaker than nondeterministic tree-walking automata.},
Author = {Boja{\'n}czyk, Miko{\l}aj and Colcombet, Thomas},
Booktitle = {ICALP 2004: Automata, Languages and Programming: 31st International Colloquium},
Date-Added = {2013-04-22 12:59:39 +0000},
Date-Modified = {2013-04-22 13:45:40 +0000},
Editor = {Josep D\'{\i}az and Juhani Karhum{\"a}ki and Arto Lepist{\"o} and Donald Sannella},
Pages = {246--256},
Pdf = {Publications/ICALP04-bojanczyc-colcombet.pdf},
Publisher = springer,
Series = lncs,
Title = {Tree-walking automata cannot be determinized},
Volume = {3142},
Year = {2004},
Bdsk-File-1 = {YnBsaXN0MDDUAQIDBAUGJCVYJHZlcnNpb25YJG9iamVjdHNZJGFyY2hpdmVyVCR0b3ASAAGGoKgHCBMUFRYaIVUkbnVsbNMJCgsMDRBWJGNsYXNzV05TLmtleXNaTlMub2JqZWN0c4AHog4PgAKAA6IREoAEgAVccmVsYXRpdmVQYXRoWWFsaWFzRGF0YV8QLy4uL1B1YmxpY2F0aW9ucy9JQ0FMUDA0LWJvamFuY3p5Yy1jb2xjb21iZXQucGRm0gkXGBlXTlMuZGF0YYAGTxECGgAAAAACGgACAAAMTWFjaW50b3NoIEhEAAAAAAAAAAAAAAAAAAAAyjyNI0grAAAACfuGH0lDQUxQMDQtYm9qYW5jenljLWNvbGNvbWJldC5wZGYAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAKBBPKq15HAAAAAAAAAAAAAQACAAAJIAAAAAAAAAAAAAAAAAAAAAxQdWJsaWNhdGlvbnMAEAAIAADKPHEDAAAAEQAIAADKq0InAAAAAQAYAAn7hgAJ+WMACfi2AAn4dAAFAP4AAL8xAAIAbE1hY2ludG9zaCBIRDpVc2VyczoAdGhvbWFzY29sY29tYmV0OgBCb3Vsb3Q6AFdlYjoAcHVibGljX2h0bWw6AFB1YmxpY2F0aW9uczoASUNBTFAwNC1ib2phbmN6eWMtY29sY29tYmV0LnBkZgAOAEAAHwBJAEMAQQBMAFAAMAA0AC0AYgBvAGoAYQBuAGMAegB5AGMALQBjAG8AbABjAG8AbQBiAGUAdAAuAHAAZABmAA8AGgAMAE0AYQBjAGkAbgB0AG8AcwBoACAASABEABIAWVVzZXJzL3Rob21hc2NvbGNvbWJldC9Cb3Vsb3QvV2ViL3B1YmxpY19odG1sL1B1YmxpY2F0aW9ucy9JQ0FMUDA0LWJvamFuY3p5Yy1jb2xjb21iZXQucGRmAAATAAEvAAAVAAIAFv//AADSGxwdHlokY2xhc3NuYW1lWCRjbGFzc2VzXU5TTXV0YWJsZURhdGGjHR8gVk5TRGF0YVhOU09iamVjdNIbHCIjXE5TRGljdGlvbmFyeaIiIF8QD05TS2V5ZWRBcmNoaXZlctEmJ1Ryb290gAEACAARABoAIwAtADIANwBAAEYATQBUAFwAZwBpAGwAbgBwAHMAdQB3AIQAjgDAAMUAzQDPAu0C8gL9AwYDFAMYAx8DKAMtAzoDPQNPA1IDVwAAAAAAAAIBAAAAAAAAACgAAAAAAAAAAAAAAAAAAANZ},
Bdsk-Url-1 = {http://dx.doi.org/10.1007/978-3-540-27836-8_23}}
@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 = {Boja{\'n}czyk, Miko{\l}aj and Colcombet, Thomas},
Date-Added = {2013-04-22 12:59:39 +0000},
Date-Modified = {2013-04-22 13:43:47 +0000},
Fjournal = {Theoretical Computer Science},
Journal = tcs,
Number = {2-3},
Pages = {164--173},
Pdf = {Publications/TCS06-bojanczyk-colcombet.pdf},
Title = {Tree-walking automata cannot be determinized},
Volume = {350},
Year = {2006},
Bdsk-File-1 = {YnBsaXN0MDDUAQIDBAUGJCVYJHZlcnNpb25YJG9iamVjdHNZJGFyY2hpdmVyVCR0b3ASAAGGoKgHCBMUFRYaIVUkbnVsbNMJCgsMDRBWJGNsYXNzV05TLmtleXNaTlMub2JqZWN0c4AHog4PgAKAA6IREoAEgAVccmVsYXRpdmVQYXRoWWFsaWFzRGF0YV8QLS4uL1B1YmxpY2F0aW9ucy9UQ1MwNi1ib2phbmN6eWstY29sY29tYmV0LnBkZtIJFxgZV05TLmRhdGGABk8RAhIAAAAAAhIAAgAADE1hY2ludG9zaCBIRAAAAAAAAAAAAAAAAAAAAMo8jSNIKwAAAAn7hh1UQ1MwNi1ib2phbmN6eWstY29sY29tYmV0LnBkZgAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAACgQ0yqteRwAAAAAAAAAAAAEAAgAACSAAAAAAAAAAAAAAAAAAAAAMUHVibGljYXRpb25zABAACAAAyjxxAwAAABEACAAAyqtCJwAAAAEAGAAJ+4YACfljAAn4tgAJ+HQABQD+AAC/MQACAGpNYWNpbnRvc2ggSEQ6VXNlcnM6AHRob21hc2NvbGNvbWJldDoAQm91bG90OgBXZWI6AHB1YmxpY19odG1sOgBQdWJsaWNhdGlvbnM6AFRDUzA2LWJvamFuY3p5ay1jb2xjb21iZXQucGRmAA4APAAdAFQAQwBTADAANgAtAGIAbwBqAGEAbgBjAHoAeQBrAC0AYwBvAGwAYwBvAG0AYgBlAHQALgBwAGQAZgAPABoADABNAGEAYwBpAG4AdABvAHMAaAAgAEgARAASAFdVc2Vycy90aG9tYXNjb2xjb21iZXQvQm91bG90L1dlYi9wdWJsaWNfaHRtbC9QdWJsaWNhdGlvbnMvVENTMDYtYm9qYW5jenlrLWNvbGNvbWJldC5wZGYAABMAAS8AABUAAgAW//8AANIbHB0eWiRjbGFzc25hbWVYJGNsYXNzZXNdTlNNdXRhYmxlRGF0YaMdHyBWTlNEYXRhWE5TT2JqZWN00hscIiNcTlNEaWN0aW9uYXJ5oiIgXxAPTlNLZXllZEFyY2hpdmVy0SYnVHJvb3SAAQAIABEAGgAjAC0AMgA3AEAARgBNAFQAXABnAGkAbABuAHAAcwB1AHcAhACOAL4AwwDLAM0C4wLoAvMC/AMKAw4DFQMeAyMDMAMzA0UDSANNAAAAAAAAAgEAAAAAAAAAKAAAAAAAAAAAAAAAAAAAA08=},
Bdsk-Url-1 = {http://dx.doi.org/10.1016/j.tcs.2005.10.031}}
@inproceedings{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.
},
Author = {Colcombet, Thomas},
Booktitle = {ICALP 2009 (2): Automata, Languages and Programming, 36th International Colloquium},
Date-Added = {2013-04-22 12:59:39 +0000},
Date-Modified = {2013-04-22 13:26:19 +0000},
Editor = {Susanne Albers and Alberto Marchetti-Spaccamela and Yossi Matias and Sotiris E. Nikoletseas and Wolfgang Thomas},
Pages = {139--150},
Pdf = {Publications/ICALP09-colcombet.pdf},
Publisher = springer,
Series = lncs,
Title = {The theory of stabilisation monoids and regular cost functions},
Volume = {5556},
Year = {2009},
Bdsk-File-1 = {YnBsaXN0MDDUAQIDBAUGJCVYJHZlcnNpb25YJG9iamVjdHNZJGFyY2hpdmVyVCR0b3ASAAGGoKgHCBMUFRYaIVUkbnVsbNMJCgsMDRBWJGNsYXNzV05TLmtleXNaTlMub2JqZWN0c4AHog4PgAKAA6IREoAEgAVccmVsYXRpdmVQYXRoWWFsaWFzRGF0YV8QLy4uL1B1YmxpY2F0aW9ucy9JQ0FMUDA5LWNvbGNvbWJldF9zdWJtaXR0ZWQucGRm0gkXGBlXTlMuZGF0YYAGTxECGgAAAAACGgACAAAMTWFjaW50b3NoIEhEAAAAAAAAAAAAAAAAAAAAyjyNI0grAAAACfuGH0lDQUxQMDktY29sY29tYmV0X3N1Ym1pdHRlZC5wZGYAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAKBH7Kq15JAAAAAAAAAAAAAQACAAAJIAAAAAAAAAAAAAAAAAAAAAxQdWJsaWNhdGlvbnMAEAAIAADKPHEDAAAAEQAIAADKq0IpAAAAAQAYAAn7hgAJ+WMACfi2AAn4dAAFAP4AAL8xAAIAbE1hY2ludG9zaCBIRDpVc2VyczoAdGhvbWFzY29sY29tYmV0OgBCb3Vsb3Q6AFdlYjoAcHVibGljX2h0bWw6AFB1YmxpY2F0aW9uczoASUNBTFAwOS1jb2xjb21iZXRfc3VibWl0dGVkLnBkZgAOAEAAHwBJAEMAQQBMAFAAMAA5AC0AYwBvAGwAYwBvAG0AYgBlAHQAXwBzAHUAYgBtAGkAdAB0AGUAZAAuAHAAZABmAA8AGgAMAE0AYQBjAGkAbgB0AG8AcwBoACAASABEABIAWVVzZXJzL3Rob21hc2NvbGNvbWJldC9Cb3Vsb3QvV2ViL3B1YmxpY19odG1sL1B1YmxpY2F0aW9ucy9JQ0FMUDA5LWNvbGNvbWJldF9zdWJtaXR0ZWQucGRmAAATAAEvAAAVAAIAFv//AADSGxwdHlokY2xhc3NuYW1lWCRjbGFzc2VzXU5TTXV0YWJsZURhdGGjHR8gVk5TRGF0YVhOU09iamVjdNIbHCIjXE5TRGljdGlvbmFyeaIiIF8QD05TS2V5ZWRBcmNoaXZlctEmJ1Ryb290gAEACAARABoAIwAtADIANwBAAEYATQBUAFwAZwBpAGwAbgBwAHMAdQB3AIQAjgDAAMUAzQDPAu0C8gL9AwYDFAMYAx8DKAMtAzoDPQNPA1IDVwAAAAAAAAIBAAAAAAAAACgAAAAAAAAAAAAAAAAAAANZ}}
@inproceedings{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.},
Author = {Colcombet, Thomas and L{\"o}ding, Christof},
Booktitle = {ICALP 2008 (2): Automata, Languages and Programming, 35th International Colloquium},
Date-Added = {2013-04-22 12:59:39 +0000},
Date-Modified = {2013-04-22 13:25:42 +0000},
Editor = {Luca Aceto and Ivan Damg{\aa}rd and Leslie Ann Goldberg and Magn{\'u}s M. Halld{\'o}rsson and Anna Ing{\'o}lfsd{\'o}ttir and Igor Walukiewicz},
Pages = {398--409},
Pdf = {Publications/ICALP08-colcombet-loeding.pdf},
Publisher = springer,
Series = lncs,
Title = {The non-deterministic {M}ostowski hierarchy and distance-parity automata},
Volume = {5126},
Year = {2008},
Bdsk-File-1 = {YnBsaXN0MDDUAQIDBAUGJCVYJHZlcnNpb25YJG9iamVjdHNZJGFyY2hpdmVyVCR0b3ASAAGGoKgHCBMUFRYaIVUkbnVsbNMJCgsMDRBWJGNsYXNzV05TLmtleXNaTlMub2JqZWN0c4AHog4PgAKAA6IREoAEgAVccmVsYXRpdmVQYXRoWWFsaWFzRGF0YV8QNy4uL1B1YmxpY2F0aW9ucy9JQ0FMUDA4LWNvbGNvbWJldC1sb2VkaW5nX3N1Ym1pdHRlZC5wZGbSCRcYGVdOUy5kYXRhgAZPEQIyAAAAAAIyAAIAAAxNYWNpbnRvc2ggSEQAAAAAAAAAAAAAAAAAAADKPI0jSCsAAAAJ+4YfSUNBTFAwOC1jb2xjb21iZXQtbG9lI0EwNDFBLnBkZgAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAoEGsqrXkcAAAAAAAAAAAABAAIAAAkgAAAAAAAAAAAAAAAAAAAADFB1YmxpY2F0aW9ucwAQAAgAAMo8cQMAAAARAAgAAMqrQicAAAABABgACfuGAAn5YwAJ+LYACfh0AAUA/gAAvzEAAgBsTWFjaW50b3NoIEhEOlVzZXJzOgB0aG9tYXNjb2xjb21iZXQ6AEJvdWxvdDoAV2ViOgBwdWJsaWNfaHRtbDoAUHVibGljYXRpb25zOgBJQ0FMUDA4LWNvbGNvbWJldC1sb2UjQTA0MUEucGRmAA4AUAAnAEkAQwBBAEwAUAAwADgALQBjAG8AbABjAG8AbQBiAGUAdAAtAGwAbwBlAGQAaQBuAGcAXwBzAHUAYgBtAGkAdAB0AGUAZAAuAHAAZABmAA8AGgAMAE0AYQBjAGkAbgB0AG8AcwBoACAASABEABIAYVVzZXJzL3Rob21hc2NvbGNvbWJldC9Cb3Vsb3QvV2ViL3B1YmxpY19odG1sL1B1YmxpY2F0aW9ucy9JQ0FMUDA4LWNvbGNvbWJldC1sb2VkaW5nX3N1Ym1pdHRlZC5wZGYAABMAAS8AABUAAgAW//8AANIbHB0eWiRjbGFzc25hbWVYJGNsYXNzZXNdTlNNdXRhYmxlRGF0YaMdHyBWTlNEYXRhWE5TT2JqZWN00hscIiNcTlNEaWN0aW9uYXJ5oiIgXxAPTlNLZXllZEFyY2hpdmVy0SYnVHJvb3SAAQAIABEAGgAjAC0AMgA3AEAARgBNAFQAXABnAGkAbABuAHAAcwB1AHcAhACOAMgAzQDVANcDDQMSAx0DJgM0AzgDPwNIA00DWgNdA28DcgN3AAAAAAAAAgEAAAAAAAAAKAAAAAAAAAAAAAAAAAAAA3k=},
Bdsk-Url-1 = {http://dx.doi.org/10.1007/978-3-540-70583-3_33}}
@inproceedings{CSL08:colcombet-loeding-depth-mu-calculus,
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 = {Colcombet, Thomas and L{\"o}ding, Christof},
Booktitle = {CSL 2008: Computer Science Logic, 22nd International Workshop},
Date-Added = {2013-04-22 12:59:39 +0000},
Date-Modified = {2013-04-22 13:01:16 +0000},
Editor = {Michael Kaminski and Simone Martini},
Pages = {416--430},
Publisher = springer,
Series = lncs,
Title = {The nesting-depth of disjunctive {$\mu$}-calculus for tree languages and the limitedness problem},
Volume = {5213},
Year = {2008},
Bdsk-File-1 = {YnBsaXN0MDDUAQIDBAUGJCVYJHZlcnNpb25YJG9iamVjdHNZJGFyY2hpdmVyVCR0b3ASAAGGoKgHCBMUFRYaIVUkbnVsbNMJCgsMDRBWJGNsYXNzV05TLmtleXNaTlMub2JqZWN0c4AHog4PgAKAA6IREoAEgAVccmVsYXRpdmVQYXRoWWFsaWFzRGF0YV8QNS4uL1B1YmxpY2F0aW9ucy9DU0wwOC1jb2xjb21iZXQtbG9lZGluZy1zdWJtaXR0ZWQucGRm0gkXGBlXTlMuZGF0YYAGTxECLAAAAAACLAACAAAMTWFjaW50b3NoIEhEAAAAAAAAAAAAAAAAAAAAyjyNI0grAAAACfuGH0NTTDA4LWNvbGNvbWJldC1sb2VkaSNBMDQ3Mi5wZGYAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAKBHLKq15JAAAAAAAAAAAAAQACAAAJIAAAAAAAAAAAAAAAAAAAAAxQdWJsaWNhdGlvbnMAEAAIAADKPHEDAAAAEQAIAADKq0IpAAAAAQAYAAn7hgAJ+WMACfi2AAn4dAAFAP4AAL8xAAIAbE1hY2ludG9zaCBIRDpVc2VyczoAdGhvbWFzY29sY29tYmV0OgBCb3Vsb3Q6AFdlYjoAcHVibGljX2h0bWw6AFB1YmxpY2F0aW9uczoAQ1NMMDgtY29sY29tYmV0LWxvZWRpI0EwNDcyLnBkZgAOAEwAJQBDAFMATAAwADgALQBjAG8AbABjAG8AbQBiAGUAdAAtAGwAbwBlAGQAaQBuAGcALQBzAHUAYgBtAGkAdAB0AGUAZAAuAHAAZABmAA8AGgAMAE0AYQBjAGkAbgB0AG8AcwBoACAASABEABIAX1VzZXJzL3Rob21hc2NvbGNvbWJldC9Cb3Vsb3QvV2ViL3B1YmxpY19odG1sL1B1YmxpY2F0aW9ucy9DU0wwOC1jb2xjb21iZXQtbG9lZGluZy1zdWJtaXR0ZWQucGRmAAATAAEvAAAVAAIAFv//AADSGxwdHlokY2xhc3NuYW1lWCRjbGFzc2VzXU5TTXV0YWJsZURhdGGjHR8gVk5TRGF0YVhOU09iamVjdNIbHCIjXE5TRGljdGlvbmFyeaIiIF8QD05TS2V5ZWRBcmNoaXZlctEmJ1Ryb290gAEACAARABoAIwAtADIANwBAAEYATQBUAFwAZwBpAGwAbgBwAHMAdQB3AIQAjgDGAMsA0wDVAwUDCgMVAx4DLAMwAzcDQANFA1IDVQNnA2oDbwAAAAAAAAIBAAAAAAAAACgAAAAAAAAAAAAAAAAAAANx},
Bdsk-File-2 = {YnBsaXN0MDDUAQIDBAUGJCVYJHZlcnNpb25YJG9iamVjdHNZJGFyY2hpdmVyVCR0b3ASAAGGoKgHCBMUFRYaIVUkbnVsbNMJCgsMDRBWJGNsYXNzV05TLmtleXNaTlMub2JqZWN0c4AHog4PgAKAA6IREoAEgAVccmVsYXRpdmVQYXRoWWFsaWFzRGF0YV8QKy4uL1B1YmxpY2F0aW9ucy9DU0wwOC1jb2xjb21iZXQtbG9lZGluZy5wZGbSCRcYGVdOUy5kYXRhgAZPEQIKAAAAAAIKAAIAAAxNYWNpbnRvc2ggSEQAAAAAAAAAAAAAAAAAAADKPI0jSCsAAAAJ+4YbQ1NMMDgtY29sY29tYmV0LWxvZWRpbmcucGRmAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAoEdMqrXkkAAAAAAAAAAAABAAIAAAkgAAAAAAAAAAAAAAAAAAAADFB1YmxpY2F0aW9ucwAQAAgAAMo8cQMAAAARAAgAAMqrQikAAAABABgACfuGAAn5YwAJ+LYACfh0AAUA/gAAvzEAAgBoTWFjaW50b3NoIEhEOlVzZXJzOgB0aG9tYXNjb2xjb21iZXQ6AEJvdWxvdDoAV2ViOgBwdWJsaWNfaHRtbDoAUHVibGljYXRpb25zOgBDU0wwOC1jb2xjb21iZXQtbG9lZGluZy5wZGYADgA4ABsAQwBTAEwAMAA4AC0AYwBvAGwAYwBvAG0AYgBlAHQALQBsAG8AZQBkAGkAbgBnAC4AcABkAGYADwAaAAwATQBhAGMAaQBuAHQAbwBzAGgAIABIAEQAEgBVVXNlcnMvdGhvbWFzY29sY29tYmV0L0JvdWxvdC9XZWIvcHVibGljX2h0bWwvUHVibGljYXRpb25zL0NTTDA4LWNvbGNvbWJldC1sb2VkaW5nLnBkZgAAEwABLwAAFQACABb//wAA0hscHR5aJGNsYXNzbmFtZVgkY2xhc3Nlc11OU011dGFibGVEYXRhox0fIFZOU0RhdGFYTlNPYmplY3TSGxwiI1xOU0RpY3Rpb25hcnmiIiBfEA9OU0tleWVkQXJjaGl2ZXLRJidUcm9vdIABAAgAEQAaACMALQAyADcAQABGAE0AVABcAGcAaQBsAG4AcABzAHUAdwCEAI4AvADBAMkAywLZAt4C6QLyAwADBAMLAxQDGQMmAykDOwM+A0MAAAAAAAACAQAAAAAAAAAoAAAAAAAAAAAAAAAAAAADRQ==},
Bdsk-Url-1 = {http://dx.doi.org/10.1007/978-3-540-87531-4_30}}
@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 = {2013-04-22 12:59:39 +0000},
Date-Modified = {2013-04-22 13:00:42 +0000},
Note = {To appear in the handbook ``Automata: from Mathematics to Applications''},
Title = {The Factorisation Forest Theorem},
Year = {2013},
Bdsk-File-1 = {YnBsaXN0MDDUAQIDBAUGJCVYJHZlcnNpb25YJG9iamVjdHNZJGFyY2hpdmVyVCR0b3ASAAGGoKgHCBMUFRYaIVUkbnVsbNMJCgsMDRBWJGNsYXNzV05TLmtleXNaTlMub2JqZWN0c4AHog4PgAKAA6IREoAEgAVccmVsYXRpdmVQYXRoWWFsaWFzRGF0YV8QPy4uLy4uLy4uL0N1cnJlbnQvUGVyc28vQXV0b21hdGhhSGFuZGJvb2tSYW1zZXkvaGFuZGJvb2tfZmZ0LnBkZtIJFxgZV05TLmRhdGGABk8RAfwAAAAAAfwAAgAADE1hY2ludG9zaCBIRAAAAAAAAAAAAAAAAAAAAMo8jSNIKwAAAAn7KRBoYW5kYm9va19mZnQucGRmAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAATfkLzFxdeQAAAAAAAAAAAAMABAAACSAAAAAAAAAAAAAAAAAAAAAXQXV0b21hdGhhSGFuZGJvb2tSYW1zZXkAABAACAAAyjxxAwAAABEACAAAzFxBWQAAAAEAGAAJ+ykACfk+AAn4pwAJ+HQABQD+AAC/MQACAGZNYWNpbnRvc2ggSEQ6VXNlcnM6AHRob21hc2NvbGNvbWJldDoAQm91bG90OgBDdXJyZW50OgBQZXJzbzoAQXV0b21hdGhhSGFuZGJvb2tSYW1zZXk6AGhhbmRib29rX2ZmdC5wZGYADgAiABAAaABhAG4AZABiAG8AbwBrAF8AZgBmAHQALgBwAGQAZgAPABoADABNAGEAYwBpAG4AdABvAHMAaAAgAEgARAASAFNVc2Vycy90aG9tYXNjb2xjb21iZXQvQm91bG90L0N1cnJlbnQvUGVyc28vQXV0b21hdGhhSGFuZGJvb2tSYW1zZXkvaGFuZGJvb2tfZmZ0LnBkZgAAEwABLwAAFQACABb//wAA0hscHR5aJGNsYXNzbmFtZVgkY2xhc3Nlc11OU011dGFibGVEYXRhox0fIFZOU0RhdGFYTlNPYmplY3TSGxwiI1xOU0RpY3Rpb25hcnmiIiBfEA9OU0tleWVkQXJjaGl2ZXLRJidUcm9vdIABAAgAEQAaACMALQAyADcAQABGAE0AVABcAGcAaQBsAG4AcABzAHUAdwCEAI4A0ADVAN0A3wLfAuQC7wL4AwYDCgMRAxoDHwMsAy8DQQNEA0kAAAAAAAACAQAAAAAAAAAoAAAAAAAAAAAAAAAAAAADSw==}}
@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-Added = {2013-04-22 12:59:39 +0000},
Date-Modified = {2013-04-22 12:59:39 +0000},
Note = {Unpublished},
Title = {{S}afra-like constructions for regular cost functions over finite words},
Year = 2011}
@article{ENTCS02:colcombet,
Abstract = {We study the partial algebra of typed terms with an associative commutative and idempotent operator (typed AC-terms). The originality lies in the representation of the typing policy by a graph which has a decidable monadic theory.
In this paper we show on two examples that some results on AC-terms can be raised to the level of typed AC-terms. The examples are the results on rational languages (in particular their closure by complement) and the property reachability problem for ground rewrite systems (equivalently process rewrite systems).},
Author = {Thomas Colcombet},
Date-Added = {2013-04-22 12:59:39 +0000},
Date-Modified = {2013-04-22 13:03:18 +0000},
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},
Bdsk-File-1 = {YnBsaXN0MDDUAQIDBAUGJCVYJHZlcnNpb25YJG9iamVjdHNZJGFyY2hpdmVyVCR0b3ASAAGGoKgHCBMUFRYaIVUkbnVsbNMJCgsMDRBWJGNsYXNzV05TLmtleXNaTlMub2JqZWN0c4AHog4PgAKAA6IREoAEgAVccmVsYXRpdmVQYXRoWWFsaWFzRGF0YV8QJS4uL1B1YmxpY2F0aW9ucy9FTlRDUzAyLWNvbGNvbWJldC5wZGbSCRcYGVdOUy5kYXRhgAZPEQHyAAAAAAHyAAIAAAxNYWNpbnRvc2ggSEQAAAAAAAAAAAAAAAAAAADKPI0jSCsAAAAJ+4YVRU5UQ1MwMi1jb2xjb21iZXQucGRmAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAoECMqrXkcAAAAAAAAAAAABAAIAAAkgAAAAAAAAAAAAAAAAAAAADFB1YmxpY2F0aW9ucwAQAAgAAMo8cQMAAAARAAgAAMqrQicAAAABABgACfuGAAn5YwAJ+LYACfh0AAUA/gAAvzEAAgBiTWFjaW50b3NoIEhEOlVzZXJzOgB0aG9tYXNjb2xjb21iZXQ6AEJvdWxvdDoAV2ViOgBwdWJsaWNfaHRtbDoAUHVibGljYXRpb25zOgBFTlRDUzAyLWNvbGNvbWJldC5wZGYADgAsABUARQBOAFQAQwBTADAAMgAtAGMAbwBsAGMAbwBtAGIAZQB0AC4AcABkAGYADwAaAAwATQBhAGMAaQBuAHQAbwBzAGgAIABIAEQAEgBPVXNlcnMvdGhvbWFzY29sY29tYmV0L0JvdWxvdC9XZWIvcHVibGljX2h0bWwvUHVibGljYXRpb25zL0VOVENTMDItY29sY29tYmV0LnBkZgAAEwABLwAAFQACABb//wAA0hscHR5aJGNsYXNzbmFtZVgkY2xhc3Nlc11OU011dGFibGVEYXRhox0fIFZOU0RhdGFYTlNPYmplY3TSGxwiI1xOU0RpY3Rpb25hcnmiIiBfEA9OU0tleWVkQXJjaGl2ZXLRJidUcm9vdIABAAgAEQAaACMALQAyADcAQABGAE0AVABcAGcAaQBsAG4AcABzAHUAdwCEAI4AtgC7AMMAxQK7AsACywLUAuIC5gLtAvYC+wMIAwsDHQMgAyUAAAAAAAACAQAAAAAAAAAoAAAAAAAAAAAAAAAAAAADJw==}}
@inproceedings{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 2010 (2): Automata, Languages and Programming, 37th International Colloquium},
Date-Added = {2013-04-22 12:59:39 +0000},
Date-Modified = {2013-04-22 13:27:41 +0000},
Editor = {Samson Abramsky and Cyril Gavoille and Claude Kirchner and Friedhelm {Meyer auf der Heide} and Paul G. Spirakis},
Pages = {563-574},
Pdf = {Publications/ICALP10-colcombet-kuperberg-lombardy-submitted.pdf},
Publisher = springer,
Series = lncs,
Title = {Regular Temporal Cost Functions},
Volume = {6199},
Year = {2010},
Bdsk-File-1 = {YnBsaXN0MDDUAQIDBAUGJCVYJHZlcnNpb25YJG9iamVjdHNZJGFyY2hpdmVyVCR0b3ASAAGGoKgHCBMUFRYaIVUkbnVsbNMJCgsMDRBWJGNsYXNzV05TLmtleXNaTlMub2JqZWN0c4AHog4PgAKAA6IREoAEgAVccmVsYXRpdmVQYXRoWWFsaWFzRGF0YV8QQi4uL1B1YmxpY2F0aW9ucy9JQ0FMUDEwLWNvbGNvbWJldC1rdXBlcmJlcmctbG9tYmFyZHktc3VibWl0dGVkLnBkZtIJFxgZV05TLmRhdGGABk8RAlIAAAAAAlIAAgAADE1hY2ludG9zaCBIRAAAAAAAAAAAAAAAAAAAAMo8jSNIKwAAAAn7hh9JQ0FMUDEwLWNvbGNvbWJldC1rdXAjQTA0ODEucGRmAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAACgSByqteSQAAAAAAAAAAAAEAAgAACSAAAAAAAAAAAAAAAAAAAAAMUHVibGljYXRpb25zABAACAAAyjxxAwAAABEACAAAyqtCKQAAAAEAGAAJ+4YACfljAAn4tgAJ+HQABQD+AAC/MQACAGxNYWNpbnRvc2ggSEQ6VXNlcnM6AHRob21hc2NvbGNvbWJldDoAQm91bG90OgBXZWI6AHB1YmxpY19odG1sOgBQdWJsaWNhdGlvbnM6AElDQUxQMTAtY29sY29tYmV0LWt1cCNBMDQ4MS5wZGYADgBmADIASQBDAEEATABQADEAMAAtAGMAbwBsAGMAbwBtAGIAZQB0AC0AawB1AHAAZQByAGIAZQByAGcALQBsAG8AbQBiAGEAcgBkAHkALQBzAHUAYgBtAGkAdAB0AGUAZAAuAHAAZABmAA8AGgAMAE0AYQBjAGkAbgB0AG8AcwBoACAASABEABIAbFVzZXJzL3Rob21hc2NvbGNvbWJldC9Cb3Vsb3QvV2ViL3B1YmxpY19odG1sL1B1YmxpY2F0aW9ucy9JQ0FMUDEwLWNvbGNvbWJldC1rdXBlcmJlcmctbG9tYmFyZHktc3VibWl0dGVkLnBkZgATAAEvAAAVAAIAFv//AADSGxwdHlokY2xhc3NuYW1lWCRjbGFzc2VzXU5TTXV0YWJsZURhdGGjHR8gVk5TRGF0YVhOU09iamVjdNIbHCIjXE5TRGljdGlvbmFyeaIiIF8QD05TS2V5ZWRBcmNoaXZlctEmJ1Ryb290gAEACAARABoAIwAtADIANwBAAEYATQBUAFwAZwBpAGwAbgBwAHMAdQB3AIQAjgDTANgA4ADiAzgDPQNIA1EDXwNjA2oDcwN4A4UDiAOaA50DogAAAAAAAAIBAAAAAAAAACgAAAAAAAAAAAAAAAAAAAOk},
Bdsk-File-2 = {YnBsaXN0MDDUAQIDBAUGJCVYJHZlcnNpb25YJG9iamVjdHNZJGFyY2hpdmVyVCR0b3ASAAGGoKgHCBMUFRYaIVUkbnVsbNMJCgsMDRBWJGNsYXNzV05TLmtleXNaTlMub2JqZWN0c4AHog4PgAKAA6IREoAEgAVccmVsYXRpdmVQYXRoWWFsaWFzRGF0YV8QNy4uLy4uLy4uL01lbW9zL1BhcGllcnMvQ29sY29tYmV0S3VwZXJiZXJnTG9tYmFyZHkxMC5wZGbSCRcYGVdOUy5kYXRhgAZPEQH2AAAAAAH2AAIAAAxNYWNpbnRvc2ggSEQAAAAAAAAAAAAAAAAAAADKPI0jSCsAAAAJ+SofQ29sY29tYmV0S3VwZXJiZXJnTG8jMUNFNDRDLnBkZgAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABzkTMsaPgEAAAAAAAAAAAADAAMAAAkgAAAAAAAAAAAAAAAAAAAAB1BhcGllcnMAABAACAAAyjxxAwAAABEACAAAyxov8QAAAAEAFAAJ+SoACfipAAn4dAAFAP4AAL8xAAIAXE1hY2ludG9zaCBIRDpVc2VyczoAdGhvbWFzY29sY29tYmV0OgBCb3Vsb3Q6AE1lbW9zOgBQYXBpZXJzOgBDb2xjb21iZXRLdXBlcmJlcmdMbyMxQ0U0NEMucGRmAA4AQgAgAEMAbwBsAGMAbwBtAGIAZQB0AEsAdQBwAGUAcgBiAGUAcgBnAEwAbwBtAGIAYQByAGQAeQAxADAALgBwAGQAZgAPABoADABNAGEAYwBpAG4AdABvAHMAaAAgAEgARAASAEtVc2Vycy90aG9tYXNjb2xjb21iZXQvQm91bG90L01lbW9zL1BhcGllcnMvQ29sY29tYmV0S3VwZXJiZXJnTG9tYmFyZHkxMC5wZGYAABMAAS8AABUAAgAW//8AANIbHB0eWiRjbGFzc25hbWVYJGNsYXNzZXNdTlNNdXRhYmxlRGF0YaMdHyBWTlNEYXRhWE5TT2JqZWN00hscIiNcTlNEaWN0aW9uYXJ5oiIgXxAPTlNLZXllZEFyY2hpdmVy0SYnVHJvb3SAAQAIABEAGgAjAC0AMgA3AEAARgBNAFQAXABnAGkAbABuAHAAcwB1AHcAhACOAMgAzQDVANcC0QLWAuEC6gL4AvwDAwMMAxEDHgMhAzMDNgM7AAAAAAAAAgEAAAAAAAAAKAAAAAAAAAAAAAAAAAAAAz0=}}
@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 2011 (2): Automata, Languages and Programming - 38th International Colloquium},
Date-Added = {2013-04-22 12:59:39 +0000},
Date-Modified = {2013-04-22 13:28:46 +0000},
Editor = {Luca Aceto and Monika Henzinger and Jiri Sgall},
Pages = {125-136},
Pdf = {Publications/ICALP11-carton-colcombet-puppis.pdf},
Publisher = springer,
Series = lncs,
Title = {Regular Languages of Words over Countable Linear Orderings},
Volume = {6756},
Year = {2011},
Bdsk-File-1 = {YnBsaXN0MDDUAQIDBAUGJCVYJHZlcnNpb25YJG9iamVjdHNZJGFyY2hpdmVyVCR0b3ASAAGGoKgHCBMUFRYaIVUkbnVsbNMJCgsMDRBWJGNsYXNzV05TLmtleXNaTlMub2JqZWN0c4AHog4PgAKAA6IREoAEgAVccmVsYXRpdmVQYXRoWWFsaWFzRGF0YV8QMy4uL1B1YmxpY2F0aW9ucy9JQ0FMUDExLWNhcnRvbi1jb2xjb21iZXQtcHVwcGlzLnBkZtIJFxgZV05TLmRhdGGABk8RAiYAAAAAAiYAAgAADE1hY2ludG9zaCBIRAAAAAAAAAAAAAAAAAAAAMo8jSNIKwAAAAn7hh9JQ0FMUDExLWNhcnRvbi1jb2xjbyMxOEZBQUIucGRmAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAGPqryuyZQQAAAAAAAAAAAAEAAgAACSAAAAAAAAAAAAAAAAAAAAAMUHVibGljYXRpb25zABAACAAAyjxxAwAAABEACAAAyuyLMQAAAAEAGAAJ+4YACfljAAn4tgAJ+HQABQD+AAC/MQACAGxNYWNpbnRvc2ggSEQ6VXNlcnM6AHRob21hc2NvbGNvbWJldDoAQm91bG90OgBXZWI6AHB1YmxpY19odG1sOgBQdWJsaWNhdGlvbnM6AElDQUxQMTEtY2FydG9uLWNvbGNvIzE4RkFBQi5wZGYADgBIACMASQBDAEEATABQADEAMQAtAGMAYQByAHQAbwBuAC0AYwBvAGwAYwBvAG0AYgBlAHQALQBwAHUAcABwAGkAcwAuAHAAZABmAA8AGgAMAE0AYQBjAGkAbgB0AG8AcwBoACAASABEABIAXVVzZXJzL3Rob21hc2NvbGNvbWJldC9Cb3Vsb3QvV2ViL3B1YmxpY19odG1sL1B1YmxpY2F0aW9ucy9JQ0FMUDExLWNhcnRvbi1jb2xjb21iZXQtcHVwcGlzLnBkZgAAEwABLwAAFQACABb//wAA0hscHR5aJGNsYXNzbmFtZVgkY2xhc3Nlc11OU011dGFibGVEYXRhox0fIFZOU0RhdGFYTlNPYmplY3TSGxwiI1xOU0RpY3Rpb25hcnmiIiBfEA9OU0tleWVkQXJjaGl2ZXLRJidUcm9vdIABAAgAEQAaACMALQAyADcAQABGAE0AVABcAGcAaQBsAG4AcABzAHUAdwCEAI4AxADJANEA0wL9AwIDDQMWAyQDKAMvAzgDPQNKA00DXwNiA2cAAAAAAAACAQAAAAAAAAAoAAAAAAAAAAAAAAAAAAADaQ==}}
@article{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-Added = {2013-04-22 12:59:39 +0000},
Date-Modified = {2013-04-22 13:51:49 +0000},
Journal = lmcs,
Note = {To appear.},
Pages = {{47}},
Pdf = {http://arxiv.org/pdf/1212.6937},
Title = {Regular cost functions, Part~{I}: logic and algebra over words},
Year = 2013}
@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 2010: 5th Annual IEEE Symposium on Logic in Computer Science},
Date-Added = {2013-04-22 12:59:39 +0000},
Date-Modified = {2013-04-22 13:34:52 +0000},
Pages = {70-79},
Pdf = {Publications/LICS10-colcombet-loeding-submitted.pdf},
Publisher = ieee,
Title = {Regular cost functions over finite trees},
Year = {2010},
Bdsk-File-1 = {YnBsaXN0MDDUAQIDBAUGJCVYJHZlcnNpb25YJG9iamVjdHNZJGFyY2hpdmVyVCR0b3ASAAGGoKgHCBMUFRYaIVUkbnVsbNMJCgsMDRBWJGNsYXNzV05TLmtleXNaTlMub2JqZWN0c4AHog4PgAKAA6IREoAEgAVccmVsYXRpdmVQYXRoWWFsaWFzRGF0YV8QaC4uLy4uLy4uL0N1cnJlbnQvQ2hyaXN0b2YvUmVndWxhckNvc3RzL1RyZWVzL0Nvc3QtdHJlZS1jb25mZXJlbmNlL0xJQ1MxMC1jb2xjb21iZXQtbG9lZGluZy1zdWJtaXR0ZWQucGRm0gkXGBlXTlMuZGF0YYAGTxECeAAAAAACeAACAAAMTWFjaW50b3NoIEhEAAAAAAAAAAAAAAAAAAAAyjyNI0grAAAACgcFH0xJQ1MxMC1jb2xjb21iZXQtbG9lZCNBMERFNi5wZGYAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAKDebKq15XAAAAAAAAAAAAAwAGAAAJIAAAAAAAAAAAAAAAAAAAABRDb3N0LXRyZWUtY29uZmVyZW5jZQAQAAgAAMo8cQMAAAARAAgAAMqrQjcAAAABACAACgcFAAn8mwAJ+k0ACfk1AAn4pwAJ+HQABQD+AAC/MQACAIpNYWNpbnRvc2ggSEQ6VXNlcnM6AHRob21hc2NvbGNvbWJldDoAQm91bG90OgBDdXJyZW50OgBDaHJpc3RvZjoAUmVndWxhckNvc3RzOgBUcmVlczoAQ29zdC10cmVlLWNvbmZlcmVuY2U6AExJQ1MxMC1jb2xjb21iZXQtbG9lZCNBMERFNi5wZGYADgBOACYATABJAEMAUwAxADAALQBjAG8AbABjAG8AbQBiAGUAdAAtAGwAbwBlAGQAaQBuAGcALQBzAHUAYgBtAGkAdAB0AGUAZAAuAHAAZABmAA8AGgAMAE0AYQBjAGkAbgB0AG8AcwBoACAASABEABIAfFVzZXJzL3Rob21hc2NvbGNvbWJldC9Cb3Vsb3QvQ3VycmVudC9DaHJpc3RvZi9SZWd1bGFyQ29zdHMvVHJlZXMvQ29zdC10cmVlLWNvbmZlcmVuY2UvTElDUzEwLWNvbGNvbWJldC1sb2VkaW5nLXN1Ym1pdHRlZC5wZGYAEwABLwAAFQACABb//wAA0hscHR5aJGNsYXNzbmFtZVgkY2xhc3Nlc11OU011dGFibGVEYXRhox0fIFZOU0RhdGFYTlNPYmplY3TSGxwiI1xOU0RpY3Rpb25hcnmiIiBfEA9OU0tleWVkQXJjaGl2ZXLRJidUcm9vdIABAAgAEQAaACMALQAyADcAQABGAE0AVABcAGcAaQBsAG4AcABzAHUAdwCEAI4A+QD+AQYBCAOEA4kDlAOdA6sDrwO2A78DxAPRA9QD5gPpA+4AAAAAAAACAQAAAAAAAAAoAAAAAAAAAAAAAAAAAAAD8A==}}
@inproceedings{MFCS11:colcombet-ley-puppis,
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 2011: Mathematical Foundations of Computer Science},
Date-Added = {2013-04-22 12:59:39 +0000},
Date-Modified = {2013-04-22 13:20:47 +0000},
Editor = {Filip Murlak and Piotr Sankowski},
Pages = {243-255},
Pdf = {Publications/MFCS11-colcombet-ley-puppis.pdf},
Publisher = springer,
Series = lncs,
Title = {On the Use of Guards for Logics with Data},
Volume = {6907},
Year = {2011},
Bdsk-File-1 = {YnBsaXN0MDDUAQIDBAUGJCVYJHZlcnNpb25YJG9iamVjdHNZJGFyY2hpdmVyVCR0b3ASAAGGoKgHCBMUFRYaIVUkbnVsbNMJCgsMDRBWJGNsYXNzV05TLmtleXNaTlMub2JqZWN0c4AHog4PgAKAA6IREoAEgAVccmVsYXRpdmVQYXRoWWFsaWFzRGF0YV8QLy4uL1B1YmxpY2F0aW9ucy9NRkNTMTEtY29sY29tYmV0LWxleS1wdXBwaXMucGRm0gkXGBlXTlMuZGF0YYAGTxECGgAAAAACGgACAAAMTWFjaW50b3NoIEhEAAAAAAAAAAAAAAAAAAAAyjyNI0grAAAACfuGH01GQ1MxMS1jb2xjb21iZXQtbGV5LXB1cHBpcy5wZGYAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAY+l7K7Ji5AAAAAAAAAAAAAQACAAAJIAAAAAAAAAAAAAAAAAAAAAxQdWJsaWNhdGlvbnMAEAAIAADKPHEDAAAAEQAIAADK7IqpAAAAAQAYAAn7hgAJ+WMACfi2AAn4dAAFAP4AAL8xAAIAbE1hY2ludG9zaCBIRDpVc2VyczoAdGhvbWFzY29sY29tYmV0OgBCb3Vsb3Q6AFdlYjoAcHVibGljX2h0bWw6AFB1YmxpY2F0aW9uczoATUZDUzExLWNvbGNvbWJldC1sZXktcHVwcGlzLnBkZgAOAEAAHwBNAEYAQwBTADEAMQAtAGMAbwBsAGMAbwBtAGIAZQB0AC0AbABlAHkALQBwAHUAcABwAGkAcwAuAHAAZABmAA8AGgAMAE0AYQBjAGkAbgB0AG8AcwBoACAASABEABIAWVVzZXJzL3Rob21hc2NvbGNvbWJldC9Cb3Vsb3QvV2ViL3B1YmxpY19odG1sL1B1YmxpY2F0aW9ucy9NRkNTMTEtY29sY29tYmV0LWxleS1wdXBwaXMucGRmAAATAAEvAAAVAAIAFv//AADSGxwdHlokY2xhc3NuYW1lWCRjbGFzc2VzXU5TTXV0YWJsZURhdGGjHR8gVk5TRGF0YVhOU09iamVjdNIbHCIjXE5TRGljdGlvbmFyeaIiIF8QD05TS2V5ZWRBcmNoaXZlctEmJ1Ryb290gAEACAARABoAIwAtADIANwBAAEYATQBUAFwAZwBpAGwAbgBwAHMAdQB3AIQAjgDAAMUAzQDPAu0C8gL9AwYDFAMYAx8DKAMtAzoDPQNPA1IDVwAAAAAAAAIBAAAAAAAAACgAAAAAAAAAAAAAAAAAAANZ}}
@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 = {Colcombet, Thomas and Niwi{\'n}ski, Damian},
Date-Added = {2013-04-22 12:59:39 +0000},
Date-Modified = {2013-04-22 13:44:35 +0000},
Doi = {10.1016/j.tcs.2005.10.046},
Fjournal = {Theoretical Computer Science},
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},
Bdsk-File-1 = {YnBsaXN0MDDUAQIDBAUGJCVYJHZlcnNpb25YJG9iamVjdHNZJGFyY2hpdmVyVCR0b3ASAAGGoKgHCBMUFRYaIVUkbnVsbNMJCgsMDRBWJGNsYXNzV05TLmtleXNaTlMub2JqZWN0c4AHog4PgAKAA6IREoAEgAVccmVsYXRpdmVQYXRoWWFsaWFzRGF0YV8QLC4uL1B1YmxpY2F0aW9ucy9UQ1MwNi1jb2xjb21iZXQtbml3aW5za2kucGRm0gkXGBlXTlMuZGF0YYAGTxECDgAAAAACDgACAAAMTWFjaW50b3NoIEhEAAAAAAAAAAAAAAAAAAAAyjyNI0grAAAACfuGHFRDUzA2LWNvbGNvbWJldC1uaXdpbnNraS5wZGYAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAKBDfKq15HAAAAAAAAAAAAAQACAAAJIAAAAAAAAAAAAAAAAAAAAAxQdWJsaWNhdGlvbnMAEAAIAADKPHEDAAAAEQAIAADKq0InAAAAAQAYAAn7hgAJ+WMACfi2AAn4dAAFAP4AAL8xAAIAaU1hY2ludG9zaCBIRDpVc2VyczoAdGhvbWFzY29sY29tYmV0OgBCb3Vsb3Q6AFdlYjoAcHVibGljX2h0bWw6AFB1YmxpY2F0aW9uczoAVENTMDYtY29sY29tYmV0LW5pd2luc2tpLnBkZgAADgA6ABwAVABDAFMAMAA2AC0AYwBvAGwAYwBvAG0AYgBlAHQALQBuAGkAdwBpAG4AcwBrAGkALgBwAGQAZgAPABoADABNAGEAYwBpAG4AdABvAHMAaAAgAEgARAASAFZVc2Vycy90aG9tYXNjb2xjb21iZXQvQm91bG90L1dlYi9wdWJsaWNfaHRtbC9QdWJsaWNhdGlvbnMvVENTMDYtY29sY29tYmV0LW5pd2luc2tpLnBkZgATAAEvAAAVAAIAFv//AADSGxwdHlokY2xhc3NuYW1lWCRjbGFzc2VzXU5TTXV0YWJsZURhdGGjHR8gVk5TRGF0YVhOU09iamVjdNIbHCIjXE5TRGljdGlvbmFyeaIiIF8QD05TS2V5ZWRBcmNoaXZlctEmJ1Ryb290gAEACAARABoAIwAtADIANwBAAEYATQBUAFwAZwBpAGwAbgBwAHMAdQB3AIQAjgC9AMIAygDMAt4C4wLuAvcDBQMJAxADGQMeAysDLgNAA0MDSAAAAAAAAAIBAAAAAAAAACgAAAAAAAAAAAAAAAAAAANK},
Bdsk-Url-1 = {http://dx.doi.org/10.1016/j.tcs.2005.10.046}}
@inproceedings{STACS04:colcombet-loeding,
Abstract = {We introduce top-down deterministic transducers with rational lookahead (transducer for short) working on infinite terms. We show that for such a transducer T̃, there exists an MSO-transduction T such that for any graph G, unfold(T(G)) = T̃(unfold(G)). Reciprocally, we show that if an MSO-transduction T ``preserves bisimilarity'', then there is a transducer T̃ such that for any graph G, unfold(T(G)) = T̃(unfold(G)). According to this, transducers can be seen as a complete method of implementation of MSO-transductions that preserve bisimilarity. One application is for transformations of equational systems.},
Author = {Colcombet, Thomas and L{\"o}ding, Christof},
Booktitle = {S{TACS} 2004: 21st {I}nternational {S}ymposium on {T}heoretical {A}spects of {C}omputer {S}cience},
Date-Added = {2013-04-22 12:59:39 +0000},
Date-Modified = {2013-04-22 13:17:05 +0000},
Editor = {Volker Diekert and Michel Habib},
Pages = {428--439},
Pdf = {Publications/STACS04-colcombet-loeding.pdf},
Publisher = springer,
Series = lncs,
Title = {On the expressiveness of deterministic transducers over infinite trees},
Volume = {2996},
Year = {2004},
Bdsk-File-1 = {YnBsaXN0MDDUAQIDBAUGJCVYJHZlcnNpb25YJG9iamVjdHNZJGFyY2hpdmVyVCR0b3ASAAGGoKgHCBMUFRYaIVUkbnVsbNMJCgsMDRBWJGNsYXNzV05TLmtleXNaTlMub2JqZWN0c4AHog4PgAKAA6IREoAEgAVccmVsYXRpdmVQYXRoWWFsaWFzRGF0YV8QLS4uL1B1YmxpY2F0aW9ucy9TVEFDUzA0LWNvbGNvbWJldC1sb2VkaW5nLnBkZtIJFxgZV05TLmRhdGGABk8RAhIAAAAAAhIAAgAADE1hY2ludG9zaCBIRAAAAAAAAAAAAAAAAAAAAMo8jSNIKwAAAAn7hh1TVEFDUzA0LWNvbGNvbWJldC1sb2VkaW5nLnBkZgAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAACgSTyqteSgAAAAAAAAAAAAEAAgAACSAAAAAAAAAAAAAAAAAAAAAMUHVibGljYXRpb25zABAACAAAyjxxAwAAABEACAAAyqtCKgAAAAEAGAAJ+4YACfljAAn4tgAJ+HQABQD+AAC/MQACAGpNYWNpbnRvc2ggSEQ6VXNlcnM6AHRob21hc2NvbGNvbWJldDoAQm91bG90OgBXZWI6AHB1YmxpY19odG1sOgBQdWJsaWNhdGlvbnM6AFNUQUNTMDQtY29sY29tYmV0LWxvZWRpbmcucGRmAA4APAAdAFMAVABBAEMAUwAwADQALQBjAG8AbABjAG8AbQBiAGUAdAAtAGwAbwBlAGQAaQBuAGcALgBwAGQAZgAPABoADABNAGEAYwBpAG4AdABvAHMAaAAgAEgARAASAFdVc2Vycy90aG9tYXNjb2xjb21iZXQvQm91bG90L1dlYi9wdWJsaWNfaHRtbC9QdWJsaWNhdGlvbnMvU1RBQ1MwNC1jb2xjb21iZXQtbG9lZGluZy5wZGYAABMAAS8AABUAAgAW//8AANIbHB0eWiRjbGFzc25hbWVYJGNsYXNzZXNdTlNNdXRhYmxlRGF0YaMdHyBWTlNEYXRhWE5TT2JqZWN00hscIiNcTlNEaWN0aW9uYXJ5oiIgXxAPTlNLZXllZEFyY2hpdmVy0SYnVHJvb3SAAQAIABEAGgAjAC0AMgA3AEAARgBNAFQAXABnAGkAbABuAHAAcwB1AHcAhACOAL4AwwDLAM0C4wLoAvMC/AMKAw4DFQMeAyMDMAMzA0UDSANNAAAAAAAAAgEAAAAAAAAAKAAAAAAAAAAAAAAAAAAAA08=},
Bdsk-Url-1 = {http://dx.doi.org/10.1007/978-3-540-24749-4_38}}
@inproceedings{ICALP03:carayol-colcombet,
Abstract = {According to Barthelman and Blumensath, the following families of infinite graphs are isomorphic: (1) prefix-recognisable graphs, (2) graph solutions of VR equational systems and (3) MS interpretations of regular trees. In this paper, we consider the extension of prefix-recognisable graphs to prefix-recognisable structures and of graphs solutions of VR equational systems to structures solutions of positive quantifier free definable (PQFD) equational systems. We extend Barthelman and Blumensath's result to structures parameterised by infinite graphs by proving that the following families of structures are equivalent: (1) prefix-recognisable structures restricted by a language accepted by an infinite deterministic automaton, (2) solutions of infinite PQFD equational systems and (3) MS interpretations of the unfoldings of infinite deterministic graphs. Furthermore, we show that the addition of a fuse operator, that merges several vertices together, to PQFD equational systems does not increase their expressive power.},
Author = {Carayol, Arnaud and Colcombet, Thomas},
Booktitle = {ICALP 2003: Automata, Languages and Programming, 30th International Colloquium},
Date-Added = {2013-04-22 12:59:39 +0000},
Date-Modified = {2013-04-22 13:09:55 +0000},
Editor = {Jos C. M. Baeten and Jan Karel Lenstra and Joachim Parrow and Gerhard J. Woeginger},
Pages = {599--610},
Pdf = {Publications/ICALP03-carayol-colcombet.pdf},
Publisher = springer,
Series = {Lecture Notes in Comput. Sci.},
Title = {On equivalent representations of infinite structures},
Volume = {2719},
Year = {2003},
Bdsk-File-1 = {YnBsaXN0MDDUAQIDBAUGJCVYJHZlcnNpb25YJG9iamVjdHNZJGFyY2hpdmVyVCR0b3ASAAGGoKgHCBMUFRYaIVUkbnVsbNMJCgsMDRBWJGNsYXNzV05TLmtleXNaTlMub2JqZWN0c4AHog4PgAKAA6IREoAEgAVccmVsYXRpdmVQYXRoWWFsaWFzRGF0YV8QLS4uL1B1YmxpY2F0aW9ucy9JQ0FMUDAzLWNhcmF5b2wtY29sY29tYmV0LnBkZtIJFxgZV05TLmRhdGGABk8RAhIAAAAAAhIAAgAADE1hY2ludG9zaCBIRAAAAAAAAAAAAAAAAAAAAMo8jSNIKwAAAAn7hh1JQ0FMUDAzLWNhcmF5b2wtY29sY29tYmV0LnBkZgAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAACgQRyqteRwAAAAAAAAAAAAEAAgAACSAAAAAAAAAAAAAAAAAAAAAMUHVibGljYXRpb25zABAACAAAyjxxAwAAABEACAAAyqtCJwAAAAEAGAAJ+4YACfljAAn4tgAJ+HQABQD+AAC/MQACAGpNYWNpbnRvc2ggSEQ6VXNlcnM6AHRob21hc2NvbGNvbWJldDoAQm91bG90OgBXZWI6AHB1YmxpY19odG1sOgBQdWJsaWNhdGlvbnM6AElDQUxQMDMtY2FyYXlvbC1jb2xjb21iZXQucGRmAA4APAAdAEkAQwBBAEwAUAAwADMALQBjAGEAcgBhAHkAbwBsAC0AYwBvAGwAYwBvAG0AYgBlAHQALgBwAGQAZgAPABoADABNAGEAYwBpAG4AdABvAHMAaAAgAEgARAASAFdVc2Vycy90aG9tYXNjb2xjb21iZXQvQm91bG90L1dlYi9wdWJsaWNfaHRtbC9QdWJsaWNhdGlvbnMvSUNBTFAwMy1jYXJheW9sLWNvbGNvbWJldC5wZGYAABMAAS8AABUAAgAW//8AANIbHB0eWiRjbGFzc25hbWVYJGNsYXNzZXNdTlNNdXRhYmxlRGF0YaMdHyBWTlNEYXRhWE5TT2JqZWN00hscIiNcTlNEaWN0aW9uYXJ5oiIgXxAPTlNLZXllZEFyY2hpdmVy0SYnVHJvb3SAAQAIABEAGgAjAC0AMgA3AEAARgBNAFQAXABnAGkAbABuAHAAcwB1AHcAhACOAL4AwwDLAM0C4wLoAvMC/AMKAw4DFQMeAyMDMAMzA0UDSANNAAAAAAAAAgEAAAAAAAAAKAAAAAAAAAAAAAAAAAAAA08=},
Bdsk-Url-1 = {http://dx.doi.org/10.1007/3-540-45061-0_48}}
@inproceedings{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 = {Blumensath, Achim and Colcombet, Thomas and L{\"o}ding, Christof},
Booktitle = {Logic and Automata: History and Perspectives [in Honor of Wolfgang Thomas]},
Date-Added = {2013-04-22 12:59:39 +0000},
Date-Modified = {2013-04-22 13:00:16 +0000},
Editor = {J{\"o}rg Flum and Erich Gr{\"a}del and Thomas Wilke},
Mrclass = {03B25 (03B15 03B70 03D05)},
Mrnumber = {2508741 (2011g:03024)},
Pages = {73--106},
Publisher = {Amsterdam University Press},
Series = {Texts in Logic and Games},
Title = {Logical theories and compatible operations},
Volume = {2},
Year = {2008},
Bdsk-File-1 = {YnBsaXN0MDDUAQIDBAUGJCVYJHZlcnNpb25YJG9iamVjdHNZJGFyY2hpdmVyVCR0b3ASAAGGoKgHCBMUFRYaIVUkbnVsbNMJCgsMDRBWJGNsYXNzV05TLmtleXNaTlMub2JqZWN0c4AHog4PgAKAA6IREoAEgAVccmVsYXRpdmVQYXRoWWFsaWFzRGF0YV8QNy4uL1B1YmxpY2F0aW9ucy82MHRoMDctYmx1bWVuc2F0aC1jb2xjb21iZXQtbG9lZGluZy5wZGbSCRcYGVdOUy5kYXRhgAZPEQIyAAAAAAIyAAIAAAxNYWNpbnRvc2ggSEQAAAAAAAAAAAAAAAAAAADKPI0jSCsAAAAJ+4YfNjB0aDA3LWJsdW1lbnNhdGgtY29sI0EwNDA2LnBkZgAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAoEBsqrXkcAAAAAAAAAAAABAAIAAAkgAAAAAAAAAAAAAAAAAAAADFB1YmxpY2F0aW9ucwAQAAgAAMo8cQMAAAARAAgAAMqrQicAAAABABgACfuGAAn5YwAJ+LYACfh0AAUA/gAAvzEAAgBsTWFjaW50b3NoIEhEOlVzZXJzOgB0aG9tYXNjb2xjb21iZXQ6AEJvdWxvdDoAV2ViOgBwdWJsaWNfaHRtbDoAUHVibGljYXRpb25zOgA2MHRoMDctYmx1bWVuc2F0aC1jb2wjQTA0MDYucGRmAA4AUAAnADYAMAB0AGgAMAA3AC0AYgBsAHUAbQBlAG4AcwBhAHQAaAAtAGMAbwBsAGMAbwBtAGIAZQB0AC0AbABvAGUAZABpAG4AZwAuAHAAZABmAA8AGgAMAE0AYQBjAGkAbgB0AG8AcwBoACAASABEABIAYVVzZXJzL3Rob21hc2NvbGNvbWJldC9Cb3Vsb3QvV2ViL3B1YmxpY19odG1sL1B1YmxpY2F0aW9ucy82MHRoMDctYmx1bWVuc2F0aC1jb2xjb21iZXQtbG9lZGluZy5wZGYAABMAAS8AABUAAgAW//8AANIbHB0eWiRjbGFzc25hbWVYJGNsYXNzZXNdTlNNdXRhYmxlRGF0YaMdHyBWTlNEYXRhWE5TT2JqZWN00hscIiNcTlNEaWN0aW9uYXJ5oiIgXxAPTlNLZXllZEFyY2hpdmVy0SYnVHJvb3SAAQAIABEAGgAjAC0AMgA3AEAARgBNAFQAXABnAGkAbABuAHAAcwB1AHcAhACOAMgAzQDVANcDDQMSAx0DJgM0AzgDPwNIA00DWgNdA28DcgN3AAAAAAAAAgEAAAAAAAAAKAAAAAAAAAAAAAAAAAAAA3k=}}
@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 automata theory: The result of Schutzenberger characterizing star-free languages, the theorem of factorization forests of Simon, the characterization 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 2011: Language and Automata Theory and Applications - 5th International Conference},
Date-Added = {2013-04-22 12:59:39 +0000},
Date-Modified = {2013-04-22 13:31:45 +0000},
Editor = {Adrian Horia Dediu and Shunsuke Inenaga and Carlos Mart\'{\i}n-Vide},
Note = {Invited lecture.},
Pages = {1-21},
Pdf = {Publications/LATA11_colcombet.pdf},
Publisher = springer,
Series = lncs,
Title = {{G}reen's Relations and their Use in Automata Theory},
Volume = {6638},
Year = {2011},
Bdsk-File-1 = {YnBsaXN0MDDUAQIDBAUGJCVYJHZlcnNpb25YJG9iamVjdHNZJGFyY2hpdmVyVCR0b3ASAAGGoKgHCBMUFRYaIVUkbnVsbNMJCgsMDRBWJGNsYXNzV05TLmtleXNaTlMub2JqZWN0c4AHog4PgAKAA6IREoAEgAVccmVsYXRpdmVQYXRoWWFsaWFzRGF0YV8QJC4uL1B1YmxpY2F0aW9ucy9MQVRBMTEtY29sY29tYmV0LnBkZtIJFxgZV05TLmRhdGGABk8RAe4AAAAAAe4AAgAADE1hY2ludG9zaCBIRAAAAAAAAAAAAAAAAAAAAMo8jSNIKwAAAAn7hhRMQVRBMTEtY29sY29tYmV0LnBkZgAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAACgQiyqteRwAAAAAAAAAAAAEAAgAACSAAAAAAAAAAAAAAAAAAAAAMUHVibGljYXRpb25zABAACAAAyjxxAwAAABEACAAAyqtCJwAAAAEAGAAJ+4YACfljAAn4tgAJ+HQABQD+AAC/MQACAGFNYWNpbnRvc2ggSEQ6VXNlcnM6AHRob21hc2NvbGNvbWJldDoAQm91bG90OgBXZWI6AHB1YmxpY19odG1sOgBQdWJsaWNhdGlvbnM6AExBVEExMS1jb2xjb21iZXQucGRmAAAOACoAFABMAEEAVABBADEAMQAtAGMAbwBsAGMAbwBtAGIAZQB0AC4AcABkAGYADwAaAAwATQBhAGMAaQBuAHQAbwBzAGgAIABIAEQAEgBOVXNlcnMvdGhvbWFzY29sY29tYmV0L0JvdWxvdC9XZWIvcHVibGljX2h0bWwvUHVibGljYXRpb25zL0xBVEExMS1jb2xjb21iZXQucGRmABMAAS8AABUAAgAW//8AANIbHB0eWiRjbGFzc25hbWVYJGNsYXNzZXNdTlNNdXRhYmxlRGF0YaMdHyBWTlNEYXRhWE5TT2JqZWN00hscIiNcTlNEaWN0aW9uYXJ5oiIgXxAPTlNLZXllZEFyY2hpdmVy0SYnVHJvb3SAAQAIABEAGgAjAC0AMgA3AEAARgBNAFQAXABnAGkAbABuAHAAcwB1AHcAhACOALUAugDCAMQCtgK7AsYCzwLdAuEC6ALxAvYDAwMGAxgDGwMgAAAAAAAAAgEAAAAAAAAAKAAAAAAAAAAAAAAAAAAAAyI=}}
@inproceedings{STACS12:colcombet,
Abstract = {We survey in this paper some variants of the notion of determinism, refining the spectrum between non-determinism and 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. The main results are underlined and some open problems proposed. },
Author = {Thomas Colcombet},
Booktitle = {S{TACS} 2012: 29th {I}nternational {S}ymposium on {T}heoretical {A}spects of {C}omputer {S}cience},
Date-Added = {2013-04-22 12:59:39 +0000},
Date-Modified = {2013-04-22 13:42:25 +0000},
Editor = {Christoph D{\"u}rr and Thomas Wilke},
Pages = {1-23},
Pdf = {http://drops.dagstuhl.de/opus/volltexte/2012/3386/pdf/2.pdf},
Publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik},
Series = {LIPIcs},
Title = {Forms of Determinism for Automata},
Volume = {14},
Year = {2012}}
@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.},
Author = {Thomas Colcombet},
Booktitle = {FCT 2007: Fundamentals of Computation Theory, 16th International Symposium},
Date-Added = {2013-04-22 12:59:39 +0000},
Date-Modified = {2013-04-22 12:59:39 +0000},
Editor = {Erzs{\'e}bet Csuhaj-Varj{\'u} and Zolt{\'a}n {\'E}sik},
Pages = {226--237},
Pdf = {Publications/FCT07-colcombet.pdf},
Publisher = SPRINGER,
Read = {1},
Series = LNCS,
Title = {Factorisation forests for infinite words},
Volume = {4639},
Year = {2007},
Bdsk-File-1 = {YnBsaXN0MDDUAQIDBAUGJCVYJHZlcnNpb25YJG9iamVjdHNZJGFyY2hpdmVyVCR0b3ASAAGGoKgHCBMUFRYaIVUkbnVsbNMJCgsMDRBWJGNsYXNzV05TLmtleXNaTlMub2JqZWN0c4AHog4PgAKAA6IREoAEgAVccmVsYXRpdmVQYXRoWWFsaWFzRGF0YV8QIy4uL1B1YmxpY2F0aW9ucy9GQ1QwNy1jb2xjb21iZXQucGRm0gkXGBlXTlMuZGF0YYAGTxEB6gAAAAAB6gACAAAMTWFjaW50b3NoIEhEAAAAAAAAAAAAAAAAAAAAyjyNI0grAAAACfuGE0ZDVDA3LWNvbGNvbWJldC5wZGYAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAKBHfKq15JAAAAAAAAAAAAAQACAAAJIAAAAAAAAAAAAAAAAAAAAAxQdWJsaWNhdGlvbnMAEAAIAADKPHEDAAAAEQAIAADKq0IpAAAAAQAYAAn7hgAJ+WMACfi2AAn4dAAFAP4AAL8xAAIAYE1hY2ludG9zaCBIRDpVc2VyczoAdGhvbWFzY29sY29tYmV0OgBCb3Vsb3Q6AFdlYjoAcHVibGljX2h0bWw6AFB1YmxpY2F0aW9uczoARkNUMDctY29sY29tYmV0LnBkZgAOACgAEwBGAEMAVAAwADcALQBjAG8AbABjAG8AbQBiAGUAdAAuAHAAZABmAA8AGgAMAE0AYQBjAGkAbgB0AG8AcwBoACAASABEABIATVVzZXJzL3Rob21hc2NvbGNvbWJldC9Cb3Vsb3QvV2ViL3B1YmxpY19odG1sL1B1YmxpY2F0aW9ucy9GQ1QwNy1jb2xjb21iZXQucGRmAAATAAEvAAAVAAIAFv//AADSGxwdHlokY2xhc3NuYW1lWCRjbGFzc2VzXU5TTXV0YWJsZURhdGGjHR8gVk5TRGF0YVhOU09iamVjdNIbHCIjXE5TRGljdGlvbmFyeaIiIF8QD05TS2V5ZWRBcmNoaXZlctEmJ1Ryb290gAEACAARABoAIwAtADIANwBAAEYATQBUAFwAZwBpAGwAbgBwAHMAdQB3AIQAjgC0ALkAwQDDArECtgLBAsoC2ALcAuMC7ALxAv4DAQMTAxYDGwAAAAAAAAIBAAAAAAAAACgAAAAAAAAAAAAAAAAAAAMd}}
@inproceedings{POPL00:colcombet-fradet,
Abstract = {We propose an automatic method to enforce trace properties on programs. The programmer specifies the property separately from the program; a program transformer takes the program and the property and automatically produces another ``equivalent'' pogram satisfying the property. This separation of concerns makes the program easier to develop and maintain. Our approach is both static and dynamic. It integrates static analyses in order to avoid useless transformations. On the other hand, it never rejects programs but adds dynamic checks when necessary. An important challenge is to make this dynamic enforcement as inexpensive as possible. The most obvious application domain is the enforcement of security policies. In particular, a potential use of the method is the securization of mobile code upon receipt.},
Author = {Thomas Colcombet and Pascal Fradet},
Booktitle = {POPL 00: Proceedings of the 27th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages},
Date-Added = {2013-04-22 12:59:39 +0000},
Date-Modified = {2013-04-22 13:20:00 +0000},
Editor = {Mark N. Wegman and Thomas W. Reps},
Pages = {54--66},
Pdf = {Publications/POPL00-colcombet-fradet.pdf},
Publisher = {ACM},
Title = {Enforcing Trace Properties by Program Transformation},
Year = 2000,
Bdsk-File-1 = {YnBsaXN0MDDUAQIDBAUGJCVYJHZlcnNpb25YJG9iamVjdHNZJGFyY2hpdmVyVCR0b3ASAAGGoKgHCBMUFRYaIVUkbnVsbNMJCgsMDRBWJGNsYXNzV05TLmtleXNaTlMub2JqZWN0c4AHog4PgAKAA6IREoAEgAVccmVsYXRpdmVQYXRoWWFsaWFzRGF0YV8QKy4uL1B1YmxpY2F0aW9ucy9QT1BMMDAtY29sY29tYmV0LWZyYWRldC5wZGbSCRcYGVdOUy5kYXRhgAZPEQIKAAAAAAIKAAIAAAxNYWNpbnRvc2ggSEQAAAAAAAAAAAAAAAAAAADKPI0jSCsAAAAJ+4YbUE9QTDAwLWNvbGNvbWJldC1mcmFkZXQucGRmAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAoELcqrXkcAAAAAAAAAAAABAAIAAAkgAAAAAAAAAAAAAAAAAAAADFB1YmxpY2F0aW9ucwAQAAgAAMo8cQMAAAARAAgAAMqrQicAAAABABgACfuGAAn5YwAJ+LYACfh0AAUA/gAAvzEAAgBoTWFjaW50b3NoIEhEOlVzZXJzOgB0aG9tYXNjb2xjb21iZXQ6AEJvdWxvdDoAV2ViOgBwdWJsaWNfaHRtbDoAUHVibGljYXRpb25zOgBQT1BMMDAtY29sY29tYmV0LWZyYWRldC5wZGYADgA4ABsAUABPAFAATAAwADAALQBjAG8AbABjAG8AbQBiAGUAdAAtAGYAcgBhAGQAZQB0AC4AcABkAGYADwAaAAwATQBhAGMAaQBuAHQAbwBzAGgAIABIAEQAEgBVVXNlcnMvdGhvbWFzY29sY29tYmV0L0JvdWxvdC9XZWIvcHVibGljX2h0bWwvUHVibGljYXRpb25zL1BPUEwwMC1jb2xjb21iZXQtZnJhZGV0LnBkZgAAEwABLwAAFQACABb//wAA0hscHR5aJGNsYXNzbmFtZVgkY2xhc3Nlc11OU011dGFibGVEYXRhox0fIFZOU0RhdGFYTlNPYmplY3TSGxwiI1xOU0RpY3Rpb25hcnmiIiBfEA9OU0tleWVkQXJjaGl2ZXLRJidUcm9vdIABAAgAEQAaACMALQAyADcAQABGAE0AVABcAGcAaQBsAG4AcABzAHUAdwCEAI4AvADBAMkAywLZAt4C6QLyAwADBAMLAxQDGQMmAykDOwM+A0MAAAAAAAACAQAAAAAAAAAoAAAAAAAAAAAAAAAAAAADRQ==}}
@inproceedings{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 = {Boja{\'n}czyk, Miko{\l}aj and Colcombet, Thomas},
Booktitle = {LICS 06: 21th IEEE Symposium on Logic in Computer Science},
Date-Added = {2013-04-22 12:59:39 +0000},
Date-Modified = {2013-04-22 13:33:43 +0000},
Pages = {285-296},
Pdf = {Publications/LICS06-bojanczyk-colcombet.pdf},
Publisher = ieee,
Title = {Bounds in $\omega$-regularity},
Year = 2006,
Bdsk-File-1 = {YnBsaXN0MDDUAQIDBAUGJCVYJHZlcnNpb25YJG9iamVjdHNZJGFyY2hpdmVyVCR0b3ASAAGGoKgHCBMUFRYaIVUkbnVsbNMJCgsMDRBWJGNsYXNzV05TLmtleXNaTlMub2JqZWN0c4AHog4PgAKAA6IREoAEgAVccmVsYXRpdmVQYXRoWWFsaWFzRGF0YV8QLi4uL1B1YmxpY2F0aW9ucy9MSUNTMDYtYm9qYW5jenlrLWNvbGNvbWJldC5wZGbSCRcYGVdOUy5kYXRhgAZPEQIWAAAAAAIWAAIAAAxNYWNpbnRvc2ggSEQAAAAAAAAAAAAAAAAAAADKPI0jSCsAAAAJ+4YeTElDUzA2LWJvamFuY3p5ay1jb2xjb21iZXQucGRmAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAoEI8qrXkcAAAAAAAAAAAABAAIAAAkgAAAAAAAAAAAAAAAAAAAADFB1YmxpY2F0aW9ucwAQAAgAAMo8cQMAAAARAAgAAMqrQicAAAABABgACfuGAAn5YwAJ+LYACfh0AAUA/gAAvzEAAgBrTWFjaW50b3NoIEhEOlVzZXJzOgB0aG9tYXNjb2xjb21iZXQ6AEJvdWxvdDoAV2ViOgBwdWJsaWNfaHRtbDoAUHVibGljYXRpb25zOgBMSUNTMDYtYm9qYW5jenlrLWNvbGNvbWJldC5wZGYAAA4APgAeAEwASQBDAFMAMAA2AC0AYgBvAGoAYQBuAGMAegB5AGsALQBjAG8AbABjAG8AbQBiAGUAdAAuAHAAZABmAA8AGgAMAE0AYQBjAGkAbgB0AG8AcwBoACAASABEABIAWFVzZXJzL3Rob21hc2NvbGNvbWJldC9Cb3Vsb3QvV2ViL3B1YmxpY19odG1sL1B1YmxpY2F0aW9ucy9MSUNTMDYtYm9qYW5jenlrLWNvbGNvbWJldC5wZGYAEwABLwAAFQACABb//wAA0hscHR5aJGNsYXNzbmFtZVgkY2xhc3Nlc11OU011dGFibGVEYXRhox0fIFZOU0RhdGFYTlNPYmplY3TSGxwiI1xOU0RpY3Rpb25hcnmiIiBfEA9OU0tleWVkQXJjaGl2ZXLRJidUcm9vdIABAAgAEQAaACMALQAyADcAQABGAE0AVABcAGcAaQBsAG4AcABzAHUAdwCEAI4AvwDEAMwAzgLoAu0C+AMBAw8DEwMaAyMDKAM1AzgDSgNNA1IAAAAAAAACAQAAAAAAAAAoAAAAAAAAAAAAAAAAAAADVA==}}
@inproceedings{STACS13:colcombet_daviaud,
Abstract = {Distance automata are automata weighted over the tropical semiring (NU{infinity},min,+). Such automata compute functions from words to NU{infinity}. It is known that testing f0 and f, g computed by distance automata answers "yes" if f<(1-epsilon)g, "no" if there is a word w such that f(w)>g(w), and may answer "yes" or "no" in all other cases. This result highly refines previously known decidability results of the same type.
The core argument behind this quasi-decision procedure is an algorithm which is able to provide an approximated finite presentation to the closure under products of sets of matrices over the tropical semiring. We also provide another theorem of affine domination which shows that previously known decision procedures for cost-automata have an improved precision when used over distance automata.},
Author = {Colcombet, Thomas and Daviaud, Laure},
Booktitle = {STACS 2013: 30th {I}nternational {S}ymposium on {T}heoretical {A}spects of {C}omputer {S}cience},
Date-Added = {2013-04-22 12:59:39 +0000},
Date-Modified = {2013-04-22 13:18:16 +0000},
Editor = {Natacha Portier and Thomas Wilke},
Pages = {574-585},
Pdf = {http://drops.dagstuhl.de/opus/volltexte/2013/3966/pdf/54.pdf},
Publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik},
Series = {LIPIcs},
Title = {Approximate Comparison of Distance Automata},
Volume = {20},
Year = {2013}}
@inproceedings{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.
},
Author = {Colcombet, Thomas and Zdanowski, Konrad},
Booktitle = {ICALP 2009 (2): Automata, Languages and Programming, 36th International Colloquium},
Date-Added = {2013-04-22 12:59:39 +0000},
Date-Modified = {2013-04-22 13:27:06 +0000},
Editor = {Susanne Albers and Alberto Marchetti-Spaccamela and Yossi Matias and Sotiris E. Nikoletseas and Wolfgang Thomas},
Pages = {151--162},
Pdf = {Publications/ICALP09-colcombet-zdanowski.pdf},
Publisher = springer,
Series = lncs,
Title = {A tight lower bound for determinization of transition labeled {B}\"uchi automata},
Volume = {5556},
Year = {2009},
Bdsk-File-1 = {YnBsaXN0MDDUAQIDBAUGJCVYJHZlcnNpb25YJG9iamVjdHNZJGFyY2hpdmVyVCR0b3ASAAGGoKgHCBMUFRYaIVUkbnVsbNMJCgsMDRBWJGNsYXNzV05TLmtleXNaTlMub2JqZWN0c4AHog4PgAKAA6IREoAEgAVccmVsYXRpdmVQYXRoWWFsaWFzRGF0YV8QOS4uL1B1YmxpY2F0aW9ucy9JQ0FMUDA5LWNvbGNvbWJldC16ZGFub3dza2lfc3VibWl0dGVkLnBkZtIJFxgZV05TLmRhdGGABk8RAjgAAAAAAjgAAgAADE1hY2ludG9zaCBIRAAAAAAAAAAAAAAAAAAAAMo8jSNIKwAAAAn7hh9JQ0FMUDA5LWNvbGNvbWJldC16ZGEjQTA0MUUucGRmAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAACgQeyqteRwAAAAAAAAAAAAEAAgAACSAAAAAAAAAAAAAAAAAAAAAMUHVibGljYXRpb25zABAACAAAyjxxAwAAABEACAAAyqtCJwAAAAEAGAAJ+4YACfljAAn4tgAJ+HQABQD+AAC/MQACAGxNYWNpbnRvc2ggSEQ6VXNlcnM6AHRob21hc2NvbGNvbWJldDoAQm91bG90OgBXZWI6AHB1YmxpY19odG1sOgBQdWJsaWNhdGlvbnM6AElDQUxQMDktY29sY29tYmV0LXpkYSNBMDQxRS5wZGYADgBUACkASQBDAEEATABQADAAOQAtAGMAbwBsAGMAbwBtAGIAZQB0AC0AegBkAGEAbgBvAHcAcwBrAGkAXwBzAHUAYgBtAGkAdAB0AGUAZAAuAHAAZABmAA8AGgAMAE0AYQBjAGkAbgB0AG8AcwBoACAASABEABIAY1VzZXJzL3Rob21hc2NvbGNvbWJldC9Cb3Vsb3QvV2ViL3B1YmxpY19odG1sL1B1YmxpY2F0aW9ucy9JQ0FMUDA5LWNvbGNvbWJldC16ZGFub3dza2lfc3VibWl0dGVkLnBkZgAAEwABLwAAFQACABb//wAA0hscHR5aJGNsYXNzbmFtZVgkY2xhc3Nlc11OU011dGFibGVEYXRhox0fIFZOU0RhdGFYTlNPYmplY3TSGxwiI1xOU0RpY3Rpb25hcnmiIiBfEA9OU0tleWVkQXJjaGl2ZXLRJidUcm9vdIABAAgAEQAaACMALQAyADcAQABGAE0AVABcAGcAaQBsAG4AcABzAHUAdwCEAI4AygDPANcA2QMVAxoDJQMuAzwDQANHA1ADVQNiA2UDdwN6A38AAAAAAAACAQAAAAAAAAAoAAAAAAAAAAAAAAAAAAADgQ==},
Bdsk-File-2 = {YnBsaXN0MDDUAQIDBAUGJCVYJHZlcnNpb25YJG9iamVjdHNZJGFyY2hpdmVyVCR0b3ASAAGGoKgHCBMUFRYaIVUkbnVsbNMJCgsMDRBWJGNsYXNzV05TLmtleXNaTlMub2JqZWN0c4AHog4PgAKAA6IREoAEgAVccmVsYXRpdmVQYXRoWWFsaWFzRGF0YV8QLy4uL1B1YmxpY2F0aW9ucy9JQ0FMUDA5LWNvbGNvbWJldC16ZGFub3dza2kucGRm0gkXGBlXTlMuZGF0YYAGTxECGgAAAAACGgACAAAMTWFjaW50b3NoIEhEAAAAAAAAAAAAAAAAAAAAyjyNI0grAAAACfuGH0lDQUxQMDktY29sY29tYmV0LXpkYW5vd3NraS5wZGYAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAKBBvKq15HAAAAAAAAAAAAAQACAAAJIAAAAAAAAAAAAAAAAAAAAAxQdWJsaWNhdGlvbnMAEAAIAADKPHEDAAAAEQAIAADKq0InAAAAAQAYAAn7hgAJ+WMACfi2AAn4dAAFAP4AAL8xAAIAbE1hY2ludG9zaCBIRDpVc2VyczoAdGhvbWFzY29sY29tYmV0OgBCb3Vsb3Q6AFdlYjoAcHVibGljX2h0bWw6AFB1YmxpY2F0aW9uczoASUNBTFAwOS1jb2xjb21iZXQtemRhbm93c2tpLnBkZgAOAEAAHwBJAEMAQQBMAFAAMAA5AC0AYwBvAGwAYwBvAG0AYgBlAHQALQB6AGQAYQBuAG8AdwBzAGsAaQAuAHAAZABmAA8AGgAMAE0AYQBjAGkAbgB0AG8AcwBoACAASABEABIAWVVzZXJzL3Rob21hc2NvbGNvbWJldC9Cb3Vsb3QvV2ViL3B1YmxpY19odG1sL1B1YmxpY2F0aW9ucy9JQ0FMUDA5LWNvbGNvbWJldC16ZGFub3dza2kucGRmAAATAAEvAAAVAAIAFv//AADSGxwdHlokY2xhc3NuYW1lWCRjbGFzc2VzXU5TTXV0YWJsZURhdGGjHR8gVk5TRGF0YVhOU09iamVjdNIbHCIjXE5TRGljdGlvbmFyeaIiIF8QD05TS2V5ZWRBcmNoaXZlctEmJ1Ryb290gAEACAARABoAIwAtADIANwBAAEYATQBUAFwAZwBpAGwAbgBwAHMAdQB3AIQAjgDAAMUAzQDPAu0C8gL9AwYDFAMYAx8DKAMtAzoDPQNPA1IDVwAAAAAAAAIBAAAAAAAAACgAAAAAAAAAAAAAAAAAAANZ}}
@inproceedings{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.},
Author = {Colcombet, Thomas},
Booktitle = {ICALP 2007: Automata, Languages and Programming, 34th International Colloquium},
Date-Added = {2013-04-22 12:59:39 +0000},
Date-Modified = {2013-04-22 13:25:05 +0000},
Editor = {Lars Arge and Christian Cachin and Tomasz Jurdzinski and Andrzej Tarlecki},
Pages = {901--912},
Pdf = {Publications/ICALP07-colcombet.pdf},
Publisher = springer,
Series = lncs,
Title = {A combinatorial theorem for trees: applications to monadic logic and infinite structures},
Volume = {4596},
Year = {2007},
Bdsk-File-1 = {YnBsaXN0MDDUAQIDBAUGJCVYJHZlcnNpb25YJG9iamVjdHNZJGFyY2hpdmVyVCR0b3ASAAGGoKgHCBMUFRYaIVUkbnVsbNMJCgsMDRBWJGNsYXNzV05TLmtleXNaTlMub2JqZWN0c4AHog4PgAKAA6IREoAEgAVccmVsYXRpdmVQYXRoWWFsaWFzRGF0YV8QJS4uL1B1YmxpY2F0aW9ucy9JQ0FMUDA3LWNvbGNvbWJldC5wZGbSCRcYGVdOUy5kYXRhgAZPEQHyAAAAAAHyAAIAAAxNYWNpbnRvc2ggSEQAAAAAAAAAAAAAAAAAAADKPI0jSCsAAAAJ+4YVSUNBTFAwNy1jb2xjb21iZXQucGRmAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAoEFMqrXkcAAAAAAAAAAAABAAIAAAkgAAAAAAAAAAAAAAAAAAAADFB1YmxpY2F0aW9ucwAQAAgAAMo8cQMAAAARAAgAAMqrQicAAAABABgACfuGAAn5YwAJ+LYACfh0AAUA/gAAvzEAAgBiTWFjaW50b3NoIEhEOlVzZXJzOgB0aG9tYXNjb2xjb21iZXQ6AEJvdWxvdDoAV2ViOgBwdWJsaWNfaHRtbDoAUHVibGljYXRpb25zOgBJQ0FMUDA3LWNvbGNvbWJldC5wZGYADgAsABUASQBDAEEATABQADAANwAtAGMAbwBsAGMAbwBtAGIAZQB0AC4AcABkAGYADwAaAAwATQBhAGMAaQBuAHQAbwBzAGgAIABIAEQAEgBPVXNlcnMvdGhvbWFzY29sY29tYmV0L0JvdWxvdC9XZWIvcHVibGljX2h0bWwvUHVibGljYXRpb25zL0lDQUxQMDctY29sY29tYmV0LnBkZgAAEwABLwAAFQACABb//wAA0hscHR5aJGNsYXNzbmFtZVgkY2xhc3Nlc11OU011dGFibGVEYXRhox0fIFZOU0RhdGFYTlNPYmplY3TSGxwiI1xOU0RpY3Rpb25hcnmiIiBfEA9OU0tleWVkQXJjaGl2ZXLRJidUcm9vdIABAAgAEQAaACMALQAyADcAQABGAE0AVABcAGcAaQBsAG4AcABzAHUAdwCEAI4AtgC7AMMAxQK7AsACywLUAuIC5gLtAvYC+wMIAwsDHQMgAyUAAAAAAAACAQAAAAAAAAAoAAAAAAAAAAAAAAAAAAADJw==},
Bdsk-Url-1 = {http://dx.doi.org/10.1007/978-3-540-73420-8_77}}
@inproceedings{CSR13:colcombet,
Abstract = {Gurevich and Rabinovich raised the following question: given a property of a set of rational numbers definable in the real line by a monadic second-order formula, is it possible to define it directly in the rational line? In other words, is it true that the presence of reals at the background do not increase the expressive power of monadic second-order logic?
In this paper, we answer positively this question. The proof in itself is a simple application of classical and more recent techniques. This question will guide us in a tour of results and ideas related to monadic theories of linear orderings.},
Author = {Thomas Colcombet},
Booktitle = {CSR},
Date-Added = {2013-02-28 12:05:33 +0000},
Date-Modified = {2013-04-22 13:40:09 +0000},
Pdf = {Publications/CSR13-colcombet-enhanced-version.pdf},
Publisher = springer,
Series = lncs,
Title = {Composition with algebra in the background},
Year = {2013}}
@unpublished{LICS13:colcombet-loeding-kuperberg-vandenboom,
Abstract = {Weakly definable languages of infinite trees are an expressive subclass of regular tree languages definable in terms of weak monadic second-order logic, or equivalently weak alternating automata. Our main result is that given a B{\"u}chi automaton, it is decidable whether the language is weakly definable. We also show that given a parity automaton, it is decidable whether the language is recognizable by a nondeterministic co-B{\"u}chi automaton.
The decidability proofs build on recent results about cost automata over infinite trees. These automata use counters to define functions from infinite trees to the natural numbers extended with infinity. We reduce to testing whether the functions defined by certain "quasi-weak" cost automata are bounded by a finite value.},
Author = {Thomas Colcombet and Christof L{\"o}ding and Denis Kuperberg and Michael Vanden Boom},
Date-Added = {2013-02-28 12:03:48 +0000},
Date-Modified = {2013-04-08 21:00:11 +0000},
Note = {in preparation},
Title = {Deciding the weak definability of B{\"u}chi definable tree languages},
Year = {2013}}
@inproceedings{LICS13:colcombet,
Abstract = {Cost monadic logic extends monadic second-order logic with the ability to measure the cardinal of sets. In particular, it allows to decide problems related to boundedness questions. In this paper, we provide new decidability results allowing the systematic investigation of questions involving ``relative boundedness''.
The first contribution in this work is to introduce a suitable logic for such questions. The second is to show the decidability of this logic over finite words. The third contribution is the use of non-standard analysis: we advacate that developing the proofs in the axiomatic system of ``relative internal set theory''
entails a significant simplification of the proofs.},
Author = {Thomas Colcombet},
Booktitle = {LICS},
Date-Added = {2013-02-28 12:03:04 +0000},
Date-Modified = {2013-04-08 20:32:05 +0000},
Title = {Cost Functions with Several Orders of Magnitudes and the use of Relative Internal Set Theory},
Year = {2013}}
@unpublished{ICALP13-submit:colcombet-goeller-manuel,
Abstract = {B-automata are automata that can compute functions from words to non-negative integers or infinity. In this paper we give another semantics to the hierarchical variant of these automata. This new semantics is equivalent to the classical one in the terminology of cost functions: functions computed are equivalent up to a polynomial factor. We provide three applications of the technique.
Our first application shows that it is possible to evaluate, reading once the word from left to right, in deterministic logspace, a B-automaton with the new semantics. A similar evaluation would require polynomial space with the original semantics.
Our second theorem shows that for games with hB-quantitative objectives, there are positional determinacy strategies that are uniformly optimal, i.e., optimal from any starting point.
Finally, we introduce a new form of history-determinism that is uniform in the sense that translation strategies are independent from bounds. We show that uniform history-determinism cannot be enforced for usual B-automata, and we disclose new forms of (equivalent) automata that have this property.},
Author = {Thomas Colcombet and Stefan G{\"o}ller and Amaldev Manuel},
Date-Added = {2013-02-28 12:01:02 +0000},
Date-Modified = {2013-02-28 20:39:38 +0000},
Note = {Submitted},
Title = {Uniformization Results on Regular Cost Functions},
Year = {2013}}
@unpublished{ICALP13-submit:colcombet-manuel,
Abstract = {We introduce and explore various fragments of mu-calculus on data words. We show that full mu-calculus is undecidable, but its nu-fragment is decidable by reduction to Data automata.
We disclose two subclasses of the nu-fragment that enjoy the further property of being closed under complementation, namely the class of Bounded Reversal (BR) and the weaker class of Bounded Mode Alternation (BMA). The later is already sufficiently expressive for capturing several logics studied in the literature, FO2
and Data-LTL. We then characterize these two fragments in terms of cascades of suitably defined automata models. },
Author = {Thomas Colcombet and Amaldev Manuel},
Date-Added = {2013-02-28 12:00:08 +0000},
Date-Modified = {2013-02-28 20:39:41 +0000},
Note = {Submitted},
Title = {mu-Calculus on Data Words},
Year = {2013}}
@unpublished{ICALP13-submit:blumensath-colcombet-kuperberg-vandenboom,
Abstract = {Regular cost functions provide a quantitative extension of regular languages that retains most of their important properties, such as expressive power and decidability, at least over finite and infinite words and over finite trees. Much less is known over infinite trees.
We consider cost functions over infinite trees defined by an extension of weak monadic second-order logic with a new fixed-point-like operator. We show this logic is decidable, improving previously known decidability results for cost logics over infinite trees. The proof relies on an equivalence with a form of automaton with counters called quasi-weak cost automata, as well as results about converting two-way alternating cost automata to one-way alternating cost automata.},
Author = {Achim Blumensath and Thomas Colcombet and Denis Kuperberg and Michael Vanden Boom},
Date-Added = {2013-02-28 11:58:33 +0000},
Date-Modified = {2013-02-28 20:39:34 +0000},
Note = {Submitted},
Title = {Two-Way Cost Automata and Cost Logics over Infinite Trees},
Year = {2013}}
@unpublished{ICALP13-submit:blumensath-carton-colcombet,
Abstract = {This paper continues a research programme on the development of decidable extensions of monadic second-order logic in the spirit of the logic MSO+U.
We introduce an extension of monadic second-order logic, asymptotic monadic second-order logic (AMSO), which refers to structures whose elements are weighted with non-negative integers and which can express constraints on these values.
We provide several results concerning the expressive power of this logic over weighted infinite words, the most important being
(1) the "equivalence" of a natural extension of it, EAMSO, with MSO+U;
(2) the proof that AMSO reaches arbitrarily high in the projective hierarchy;
(3) the equivalence of the "number-prenex fragment of AMSO" with WAMSO, the weak fragment of AMSO;
(4) the proof that WAMSO reaches all finite levels of the Borel hierarchy;
(5) new forms of tiling problems which are equivalent to the satisfiability of WAMSO.
Our conjecture is that the satisfiability of AMSO is decidable (as for MSOpU).
We believe it may be significantly simpler to solve this conjecture for \AMSO than
for MSOpU. The weak fragment is a promising intermediate step.},
Author = {Achim Blumensath and Olivier Carton and Thomas Colcombet},
Date-Added = {2013-02-28 11:56:01 +0000},
Date-Modified = {2013-02-28 20:39:31 +0000},
Note = {Submitted},
Title = {Asymptotic Monadic Second-Order Logic},
Year = {2013}}
@unpublished{Habilitation2013:colcombet,
Abstract = {This thesis gives a broad picture of the theory of regular cost functions. Regular cost functions are quantitative extensions to regular languages. A cost function is a function from words (or trees. . .) to the non-negative integers or infinity. These functions are considered modulo an equivalence relation that allows some distortion of the exact values, but preserves the existence of bounds.
Regular cost functions form a sub-class that admits many effectively equivalent charac- terisations in terms of logic, automata, algebra and regular expressions. Some decidability results are deduced.
These results extend on the one hand the classical results on regular languages, and on the other hand the works of Hashiguchi, Simon, Leung, and Kirsten concerning distance automata, the tropical semiring and the star-height problem.
This document describes the current knowledge about regular cost functions for finite words, infinite words, finite trees and infinite trees.},
Author = {Thomas Colcombet},
Date-Added = {2012-12-21 17:00:39 +0000},
Date-Modified = {2013-04-22 07:26:09 +0000},
Note = {Habilitation thesis, in french},
Pdf = {Publications/habilitation-colcombet_v1.1.pdf},
Title = {Fonctions R{\'e}guli{\`e}res de Co{\^u}t},
Year = {2013}}
@conference{ICALP02:colcombet,
Abstract = {We consider a new class of infinite graphs defined as the smallest solution of equational systems with vertex replacement operators and unsynchronised product. We show that those graphs have an equivalent internal representation as graphs of recognizable ground term rewriting systems. Furthermore, we show that, when restricted to bounded tree-width, those graphs are isomorphic to hyperedge replacement equational graphs. Finally, we prove that on a wider family of graphs --- interpretations of trees having a decidable monadic theory --- the first order theory with reachability is decidable.
},
Address = {Malaga},
Author = {Thomas Colcombet},
Booktitle = {29th ICALP},
Date-Modified = {2013-04-22 13:07:18 +0000},
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}}
@phdthesis{PHD04:colcombet,
Abstract = {This work is dedicated to the study of infinite structures and graphs which admit a finite representation, to their geometrical properties as well as decidability properties concerning them. Following Courcelle's work, we focus our study on their representation as solution of equational systems.
We first introduce deterministic transducers (top-down with lookahead for infinite trees). This tool allows us to deal with infinite equational systems, thus extending some previous results, originally stated for finite equational systems.
We then study the stack based families of structures and concentrate ourselves on prefix recognizable ones. We establish various equivalent representations for them, and study their restriction to bounded tree-width. We finally consider the enrichment of those equational systems by an extra operator of fusion.
We then study structures admitting term-automatic presentations. We show once more that those structures admit various equivalent representations.
Finally, we study the family of graphs definable by ground term rewriting and establish some equivalences of representations. We conclude by a study of the nature of those graphs when restricted to bounded tree or clique width.
},
Author = {Thomas Colcombet},
Date-Modified = {2013-04-22 13:48:36 +0000},
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}
@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}}
@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},
Date-Modified = {2013-04-22 13:05:07 +0000},
Institution = {{Irisa Rennes}},
Number = {{hal-00125047}},
Pdf = {Publications/HAL07-colcombet.pdf},
Title = {{On Factorization Forests}},
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},
Date-Modified = {2013-04-22 13:35:45 +0000},
Journal = LMCS,
Number = {2},
Pages = {2:4, 36 pp. (electronic)},
Pdf = {Publications/LMCS07-colcombet-loeding.pdf},
Title = {Transforming structures by set interpretations},
Volume = {3},
Year = {2007}}
@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}
@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}}
@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}
