Publisher： Cambridge University Press
E-ISSN： 1469-8072|27|2|157-183
ISSN： 0960-1295
Source： Mathematical Structures in Computer Science, Vol.27, Iss.2, 2017-02, pp. : 157-183
Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.
Abstract
This article introduces an analogue of permutation classes in the context of polyominoes. For both permutation classes and polyomino classes, we present an original way of characterizing them by avoidance constraints (namely, with excluded submatrices) and we discuss how canonical such a description by submatrix-avoidance can be. We provide numerous examples of permutation and polyomino classes which may be defined and studied from the submatrix-avoidance point of view, and conclude with various directions for future research on this topic.
Related content
Access to resources
Recommend
A Gentle Introduction to Applications of Algorithmic Metatheorems for Space and Circuit Classes
By Tantau Till
Algorithms, Vol. 9, Iss. 3, 2016-07 ,pp. :