Combinatorics on words and digital geometry

点击翻译按钮获取中文摘要

My main research domain is combinatorics on words, where the algorithmic point of view plays an important role both on the theoretical and practical aspects. I developed my research along the following axes where combinatorics of words are central:** A. Combinatorics of infinite words ** B. Digital geometry and tilings ** C. Formal languages and applications**** A. In this area I am mostly concerned with palindromic complexity (number of distinct palindomic subwords) and subword or factor complexity (number of distinct factors). It is used for classifying words and particularly fixed points of morphisms accordingly. I also study a particular class of infinite words (called smooth) related to the exponential trajectories of Oldenburger, which include the fixed points of exponential trajectories and therefore the Kolakoski word.** B. The contour of discrete figures is encoded by the so-called Freeman chain code, a word on a 4-letter alphabet consisting of the four elementary steps in the digital plane (square grid). Combinatorics on words apply therefore directly and provide useful tools for developing new algorithms. Palindromes and finite Sturmian words again appear, since they encode respectively symmetries and line segments. Lyndon factorizations also apply in the segmentation. The case of polyominoes that tile the plane by translation is a source of numerous problems also linked with number theory. ** C. I study enumeration problems, often are enumerated by rational or algebraic languages. I also consider the problems of exhaustive and random generation of combinatorial objects.****