Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Tilings by translation: enumeration by a rational language approach. | Tilings by translation enumeration by a rational language approach Srecko Brlek Andrea Frosini 1 Simone Rinaldi 1 Laurent Vuillon Ỉ Submitted Jun 6 2005 Accepted Feb 7 2006 Published Feb 15 2006 Mathematics Subject Classification 05A15 Abstract Beauquier and Nivat introduced and gave a characterization of the class of pseudo-square polyominoes . 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 XYX 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 semiperimeter. The case of pseudo-square convex polyominoes is also analyzed. 1 Introduction The way of tiling planar surfaces has always been a fascinating problem and it has been widely studied also in ancient times for its beautiful decorative implications. Recently this problem has shown interesting mathematical aspects connected with computational theory mathematical logic and discrete geometry and tilings are often regarded as basic objects for proving undecidability results for planar problems. Furthermore they have been used in physics as powerful tools for studying quasi-crystal structures in particular these structures can be better understood by representing them as rigid tilings decorated by atoms in a uniform fashion. Their long-range order can successively be investigated in a purely tiling framework after assigning to every tiling a structural energy. Lab. Combinatoire et d Informatique Mathematique Un. Quebec Montreal CP 8888 Succ. Centreville Montreal QC Canada H3C 3P8 brlek@ iDip. di Scienze Matematiche e Informatiche Universita di Siena Pian dei Mantellini 44 Siena Italy frosini@ rinaldi@ Laboratoire de Mathematiques UMR 5127 CNRS .
