Tiling the plane with permutations

A permutomino is a polyomino uniquely determined by a pair of permutations. Recently permutominoes, and in particular convex permutominoes have been studied by several authors concerning their analytical and bijective enumeration; tomographical reconstruction, and the algebraic characterization of the associated permutations [2,3]. On the other side, Beauquier and Nivat [5] introduced and gave a characterization of the class of pseudo-square polyominoes, i.e. polyominoes that tile the plane by translation: a polyomino is called pseudo-square if its boundary word may be factorized as XYX (X) over bar(Y) over bar. In this paper we consider the pseudo-square polyominoes which are also convex permutominoes. By using the Beauquier-Nivat characterization we provide some geometrical and combinatorial properties of such objects, and we show for any fixed X, each word Y such that XY (X) over bar(Y) over bar is pseudo-square is prefix of an infinite word Y-infinity with period 4 vertical bar X vertical bar(N)vertical bar X vertical bar(E). Some conjectures obtained through exhaustive search are also presented and discussed in the final section.