Tilings by translation: enumeration by a rational language approach (Q815209)

Summary: \textit{D. Girault-Beauquier} and \textit{M. Nivat} [Topology and category theory in computer science, Proc. Conf., Oxford/UK 1989, 291--333 (1991; Zbl 0755.52008)] introduced and gave a characterization of the class of pseudo-square polyominoes, i.e. those polyominoes that tile the plane by translation: a polyomino tiles the plane by translation if and only if its boundary word \(W\) may be factorized as \(W = XY\overline X \overline Y\). In this paper we consider the subclass PSP of pseudo-square polyominoes which are also parallelogram. By using the Beauquier-Nivat characterization we provide by means of a rational language the enumeration of the subclass of psp-polyominoes with a fixed planar basis according to the semi-perimeter. The case of pseudo-square convex polyominoes is also analyzed.