I have the pleasure to write the preface of this second special issue devoted to the international conferences "WORDS". Two years after the organization of the first conference, and once more in Rouen, "WORDS" held during the whole third week of september 1999. Compared to the first edition, the number of published papers has been clearly increasing (they were about eighty participants in the conference).
It may be reasonably considered that the concept of words is one century old. Dispite of this, it is remarkable to note that, in the begining of this XXI st century, deep theoretical results continue to illustrate classical topics (like factorization of words, or variable lengths) codes and just as well as new challenging topics (like partial words, or multi-dimensional words).
All the topics that were presented are specially based on the study of words, focusing to their mathematical properties. As a matter of fact, historically, the theory of words grew up from mathematical questions, connected to famous mathematical topics, especially the combinatorical group theory, and the number theory. Moreover, the importance of the topic grew up also as egards to connections with more practical scientific domains, beggining by the technical topics of computer science itself.
This two dual linking is complex: it is in fact articulated between three level of search: the technical applicative domain, the field of models, and finally the mathematical level itself. Indeed, although in many scientific topics, words play a prominent part as a modelisation tool, the object of the theory of words appears more essentially as the study of questions concerning mathematical objects, more than the examination of questions on the models themselves. Due to this position, the theory of words remains certainly one of the nicest example of very fructuous interractions between deep theoretical questions are connected to technical applications. This is certainly why, just as from a formalist point of view or from a intuitionist conception, words constitue in my opinion a great scientific theory.
Let me now briefly present the contents of this special issue. It appears to me convenient to bring the different results in five main topics:
The study of words beyong the mathematical properties of their factor remains one of the most illustrated topic that were presented. Tom Brown wrote a very interesting survey of the different connections between sturmian words and the number theory. The notion of trapezoidal words, which is based on the concept of "special factor", is examined by Flavio d'Alessandro, who gives a characterization of those of trapezoidal words that are either sturmian or non sturmian. By considering bi-infinite words defined as an application from Z into a binary alphabet, Alex Heinis investigate the properties of the corresponding complexity function. At least, G. Richomme and F. Wlazinski consider the notion of k-power free morphism. Their contribution consists, in particular, in examining the finiteness of test-sets for such morphisms, and in investigating the connections with the morphic generation of cube-free infinite words.
Another important topic of search consists in the examination of the combinatorial properties of the words in connection with different notion of factorization. Jean Berstel and Luc Boasson draw a new combinatorial approach for studying the question of factorising a set of words as the result of a shuffle product of a suitable family of words. Commutation of the product of sets of words is investigated by Christian Choffrut, Juhani Karhumaki and Nicolas Ollinger: this study is certainly a new fundamental approach lead to formulate numerous questions. Deffect effect and Periodicity are clearly concerned by the study of different schemes of factorizations of a given word over a given family of factors: new results connecting this point of are presented by Juhani Karhumaki and Ján Manuch. The dual notion of forbidden factor, a special case of unavoidability is also concerned by the paper from Filippo Mignosi, Antonio Restivo and Maria Gabriela Sciortino.
The Theory of the variable lenght codes remains a challenging topic of search. In his paper, Aldo de Luca examines some questions of the theory by making use of a new analytic formalism. By examining the notion of so-called notion of interpretation Yannick Guesnet has introduced the new performing class of finite interpreting delay (f.i.d. for short) codes. In a new paper, he study f.i.d. codes from the point view of maximality and completeness. The notion of completeness is also the main feature of my paper, with Carla Selmi. Our results leads especially to generalise to a special notion of local completeness, famous results from Marcel-Paul Schützenberger and Maurice Nivat.
It is of interest to notice that to extend the concept of words clearly remains a concern of many searchers. In their paper, Valérie Berthé and Robert Tijdeman broache the extension, to many dimensions, of the properties connected to balancedness for words. Another important contribution is given by the survey of pseudorandom binary words from Christian Mauduit.
The last section is devoted to connections between words and other mathematical topics. These connections are numerous, since words are a powerfull modelizing concept that play a part presently in various scientific domains, such as spectral analysis, shufle algebra, Lie algebra. From this point of view, the paper of Vadim Malychev deals with the spectral analysis of Hamiltonians constructed from substitutions of finite grammars. Mickael Bigotte, Gérard Jacob, Nour Edine Ouous and Marc Petitot examine the concept of Lyndon words in connection with the behaviour of zeta values relations tables. Lie algebra are also concerned, as attested by the paper of Gérard Duchamp, Éric Laugerotte and Jean-Gabriel Luque. At least, a very interesting application of words to coding is presented in the work of Sylvia Encheva and Gérard Cohen.
To finish this introduction, I would like to thanks all the contributors. It is unusefull that I emphazise that all these tremendous topics of search, and all the very interesting results that consitue this special issue, confirm the vitality of the theory of words.
atml@free.fr | Dernière mise à jour : le 07.03.02 |