Combinatorial problems concerning words defined by morphisms and polyominoes satisfying convexity constraints

One of the main subfields of combinatorics is combinatorics on words. This work concerns the study of the Burrows-Wheeler transform (BWT) when applied to morphic words. The BWT is a popular method used for text compression, because it produces a permutation of the characters of an input word and tends to group the same characters together. We restrict our investigation to binary morphic words. The main result is that for a binary morphism µ with quadratic factorial complexity, the number of clusters of the output word ρ(bwt(µ^i(a))) is O(i), from which follows that every binary morphism is BWT-compressible. We believe that such techniques can be extended to other classes of morphisms and, consequently, this bound O(i) may also hold independently of the factorial complexity. Moreover, we are interested to characterize the morphisms for which the bound becomes Θ(i), to extend it to words on larger alphabets. Another of the main subfields of combinatorics is enumerative combinatorics. This work is about the enumeration of classes of polyominoes defined by convexity constraints by using bijective methods. We present a correspondences between directed convex polyominoes and triplets (F, G, λ), where F, G are ordered forests and λ is a monotone path, called cut. By using this correspondence and by imposing some constraints on the trees and/or on the cut, we get the enumeration of directed k-convex polyominoes with respect to their semi-perimeter for each k ≥ 1. Our porpouse is to extend this method to solve the still open problem of enumerating k-convex polyominoes with k ≥ 3. We have investigated the class C(k,1) of polyominoes with NE-degree of convexity equal to k and we have proved that there exists a bijection between C(k,1) polyominoes and pairs of forests with pairs of cuts. We also provide a decomposition of the class of C(k,1) polyominoes into subclasses obtained from k or (k+1)-parallelogram polyominoes by some particular cuts and we show a correspondence between the cells of a polyomino and the nodes of its associated pair of forests, with the purpouse of characterizing the lower cut. We believe that the method to enumerate directed k-convex polyominoes could be generalized and used to get the enumeration of C(k,1) polyominoes and, consequently, of all k-convex polyominoes.