Abstract
The notion of a pattern within a binary picture (polyomino) has been introduced and studied in [3], and resembles the notion of pattern containment within permutations. The main goal of this paper is to extend the studies of [3] by adopting a more geometrical approach: we use the notion of pattern avoidance in order to recognize or describe families of polyominoes defined by means of geometrical constraints or combinatorial properties. Moreover, we extend the notion of pattern in a polyomino, by introducing generalized polyomino patterns, so that to be able to describe more families of polyominoes known in the literature.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Barcucci, E., Frosini, A., Rinaldi, S.: On directed-convex polyominoes in a rectangle. Discrete Math. 298(1-3), 62–78 (2005)
Battaglino, D.: Enumeration of polyominoes defined in terms of pattern avoidance or convexity constraints, PhD thesis (University of Sienna), arXiv:1405.3146v1 (2014)
Battaglino, D., Bouvel, M., Frosini, A., Rinaldi, S.: Permutation classes and polyomino classes with excluded submatrices. ArXiv 1402.2260 (2014)
Battaglino, D., Bouvel, M., Frosini, A., Rinaldi, S., Socci, S., Vuillon, L.: Pattern avoiding polyominoes. In: Proceedings di Italian Conference Theoretical Computer Science, Palermo, Settembre 9-11 (2013)
Bona, M.: Combinatorics of permutations. Chapman-Hall and CRC Press (2004)
Brändén, P., Claesson, A.: Mesh patterns and the expansion of permutation statistics as sums of permutation patterns. Electr. J. of Combin. 18(2) (2011) (The Zeilberger Festschrift volume)
Brocchi, S., Frosini, A., Pinzani, R., Rinaldi, S.: A tiling system for the class of L-convex polyominoes. Theor. Comput. Sci. 457, 73–81 (2013)
Castiglione, G., Restivo, A.: Ordering and Convex Polyominoes. In: Margenstern, M. (ed.) MCU 2004. LNCS, vol. 3354, pp. 128–139. Springer, Heidelberg (2005)
Castiglione, G., Frosini, A., Munarini, E., Restivo, A., Rinaldi, S.: Combinatorial aspects of L-convex polyominoes. European J. Combin. 28, 1724–1741 (2007)
Castiglione, G., Frosini, A., Restivo, A., Rinaldi, S.: Enumeration of L-convex polyominoes by rows and columns. Theor. Comput. Sci. 347, 336–352 (2005)
Klazar, M.: On abab-free and abba-free sets partitions. European J. Combin. 17, 53–68 (1996)
Knuth, D.E.: The Art of Computer Programming, 2nd edn. Volume 1: Fundamental algorithms; Addison-Wesley Series in Computer Science and Information Processing. Addison-Wesley Publishing Co., Reading (1975)
Rowland, E.: Pattern avoidance in binary trees. J. Combin. Theory Ser. A 117, 741–758 (2010)
Sagan, B.E.: Pattern avoidance in set partitions. Ars Combin. 94, 79–96 (2010)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Battaglino, D., Frosini, A., Guerrini, V., Rinaldi, S., Socci, S. (2014). Binary Pictures with Excluded Patterns. In: Barcucci, E., Frosini, A., Rinaldi, S. (eds) Discrete Geometry for Computer Imagery. DGCI 2014. Lecture Notes in Computer Science, vol 8668. Springer, Cham. https://doi.org/10.1007/978-3-319-09955-2_3
Download citation
DOI: https://doi.org/10.1007/978-3-319-09955-2_3
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-09954-5
Online ISBN: 978-3-319-09955-2
eBook Packages: Computer ScienceComputer Science (R0)