Setting the Path to the Combinatorial Characterization of Prime Double Square Polyominoes

Moving from the seminal work of Beauquier and Nivat (1991) about the characterization of polyominoes that tile the plane by translation, Blondin Massé et al. (2013) found that their boundary words, encoded by the Freeman chain coding on a four letters alphabet, have interesting combinatorial properties. In particular, they considered the specific class of double square polyominoes, and they defined two operators that allow to generate them starting from the basic class of the so called prime double squares. However, the proposed algorithm suffers few drawbacks due to repetitions and outliers generation. Here a different combinatorial approach to the double square characterization is proposed. In particular we provide a series of properties for the boundary words of prime double square tiles, that lead to detect some factors of them where a specific letter of the alphabet never occurs. The possibility of extending this property to the whole boundary word of a prime double square, as it seems, would naturally provide a valuable characterization and a tool for their generation and enumeration.