The notion of submatrix avoidance in polyominoes has recently been introduced in [2]with the aim of extending most of the concepts and properties concerning pattern avoiding permutations to the setting of polyominoes. In this paper we use submatrix avoidance to describe families of polyominoes which, in the literature, are usually defined by means of the geometric constraints of convexity, k-convexity, and directedness. To reach this goal, we provide an extension of the notion of pattern in a polyomino, by introducing generalized polyomino patterns. In the second part of the paper, we tackle the same problem in the context of discrete sets, which can be naturally regarded as binary matrices. In this case, we consider two types of geometric constraints: convexityand directedness, and we study how these constraints can be imposed on matrices by using submatrix avoidance.
Geometric properties of matrices induced by pattern avoidance / Frosini, Andrea; Guerrini, Veronica; Rinaldi, Simone. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - STAMPA. - 624:(2016), pp. 109-120. [10.1016/j.tcs.2015.11.012]
Geometric properties of matrices induced by pattern avoidance
FROSINI, ANDREA;
2016
Abstract
The notion of submatrix avoidance in polyominoes has recently been introduced in [2]with the aim of extending most of the concepts and properties concerning pattern avoiding permutations to the setting of polyominoes. In this paper we use submatrix avoidance to describe families of polyominoes which, in the literature, are usually defined by means of the geometric constraints of convexity, k-convexity, and directedness. To reach this goal, we provide an extension of the notion of pattern in a polyomino, by introducing generalized polyomino patterns. In the second part of the paper, we tackle the same problem in the context of discrete sets, which can be naturally regarded as binary matrices. In this case, we consider two types of geometric constraints: convexityand directedness, and we study how these constraints can be imposed on matrices by using submatrix avoidance.File | Dimensione | Formato | |
---|---|---|---|
Geometric properties of matrices induced by pattern avoidance.pdf
Accesso chiuso
Tipologia:
Pdf editoriale (Version of record)
Licenza:
Tutti i diritti riservati
Dimensione
396.69 kB
Formato
Adobe PDF
|
396.69 kB | Adobe PDF | Richiedi una copia |
tcs10513.pdf
accesso aperto
Tipologia:
Altro
Licenza:
Open Access
Dimensione
283.7 kB
Formato
Adobe PDF
|
283.7 kB | Adobe PDF |
I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.