Research work · 2006

An object grammar for the class of L-convex polyominoes

Andrea Frosini, Simone Rinaldi

Florence Research (University of Florence)

Abstract

We consider the class of L-convex polyominoes, i.e. convex polyomi- noes where any two chosen cells can be connected simply using an internal path having at most one change of direction. The main result of the paper is the definition of an object grammar decomposition of this class, which gives com- binatorial evidence of the rationality of the generating function, and suggests some new combinatorial properties.