Abstract
In 2014, it was conjectured that any polyomino can be factorized uniquely as a product of prime polyominoes [7]. In this paper, we present simple tools from words combinatorics and graph topology that seem very useful in solving the conjecture. The main one is called parallelogram network, which is a particular subgraph of \(G(\mathbb {Z}^2)\) induced by a parallelogram morphism, i.e. a morphism describing the contour of a polyomino tiling the plane as a parallelogram would. In particular, we show that parallelogram networks are homeomorphic to \(G(\mathbb {Z}^2)\). This leads us to show that the image of the letters of parallelogram morphisms is a circular code provided each element is primitive, therefore solving positively a 2013 conjecture [8].
H. Tremblay—This research is supported by the Natural Sciences and Engineering Research Council of Canada (NSERC).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Anselmo, M., Giammarresi, D., Madonia, M.: Two dimensional prefix codes of pictures. In: Béal, M.-P., Carton, O. (eds.) DLT 2013. LNCS, vol. 7907, pp. 46–57. Springer, Heidelberg (2013)
Arqus, D.G., Michel, C.J.: A circular code in the protein coding genes of mitochondria. J. Theor. Biol. 189(3), 273–290 (1997). http://www.sciencedirect.com/science/article/pii/S0022519397905130
Bassino, F.: Generating functions of circular codes. Adv. Appl. Math. 22(1), 1–24 (1999)
Beauquier, D., Nivat, M.: On translating one polyomino to tile the plane. Discrete Comput. Geom. 6, 575–592 (1991)
Berstel, J., Perrin, D., Reutenauer, C.: Codes and Automata, Encyclopedia of Mathematics and Its Applications, vol. 129. Cambridge University Press, Cambridge (2009)
Berthé, V., Labbé, S.: An arithmetic and combinatorial approach to three-dimensional discrete lines. In: Debled-Rennesson, I., Domenjoud, E., Kerautret, B., Even, P. (eds.) DGCI 2011. LNCS, vol. 6607, pp. 47–58. Springer, Heidelberg (2011)
Blondin Massé, A., Tall, A.M., Tremblay, H.: On the arithmetics of discrete figures. In: Dediu, A.-H., Martín-Vide, C., Sierra-Rodríguez, J.-L., Truthe, B. (eds.) LATA 2014. LNCS, vol. 8370, pp. 198–209. Springer, Heidelberg (2014)
Massé, A.B., Garon, A., Labbé, S.: Combinatorial properties of double square tiles. Theor. Comput. Sci. 502, 98–117 (2013)
Brlek, S., Koskas, M., Provençal, X.: A linear time and space algorithm for detecting path intersection in \(\mathbb{Z}^d\). Theor. Comput. Sci. 412(36), 4841–4850 (2011)
Brlek, S., Lachaud, J., Provençal, X., Reutenauer, C.: Lyndon + Christoffel = digitally convex. Pattern Recogn. 42(10), 2239–2246 (2009)
Cousineau, G.: Characterization of some periodic tiles by contour words. Oligomerization of Chemical and Biological Compounds (2014)
Diestel, R.: Graph Theory, 4th edn. Springer, New York (2010)
Golomb, S.W., Gordon, B.: Codes with bounded synchronization delay. Inf. Control 8(4), 355–372 (1965)
Gross, J.L., Tucker, T.W.: Topological Graph Theory. Wiley, New York (1987)
Lothaire, M.: Combinatorics on Words. Cambridge University Press, Cambridge (1997)
Provençal, X.: Combinatoire des mots, géométrie discrète et pavages. Ph.D. thesis, D1715, Université du Québec à Montréal (2008)
Schtzenberger, M.: On a factorization of free monoids. Proc. Amer. Math. Soc. 16, 21–24 (1965)
Wijshoff, H., van Leeuwen, J.: Arbitrary versus periodic storage schemes and tessellations of the plane using one type of polyomino. Inf. Control 62(1), 1–25 (1984)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this paper
Cite this paper
Massé, A.B., Lapointe, M., Tremblay, H. (2016). Parallelogram Morphisms and Circular Codes. In: Dediu, AH., Janoušek, J., Martín-Vide, C., Truthe, B. (eds) Language and Automata Theory and Applications. LATA 2016. Lecture Notes in Computer Science(), vol 9618. Springer, Cham. https://doi.org/10.1007/978-3-319-30000-9_17
Download citation
DOI: https://doi.org/10.1007/978-3-319-30000-9_17
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-29999-0
Online ISBN: 978-3-319-30000-9
eBook Packages: Computer ScienceComputer Science (R0)