Constellation, le dépôt institutionnel de l'Université du Québec à Chicoutimi

Parallelogram morphisms and circular codes

Blondin Massé Alexandre, Lapointe Mélodie et Tremblay Hugo. (2016). Parallelogram morphisms and circular codes. Dans Adrian-Horia Dediu, Jan Janoušek, Carlos Martín-Vide et Bianca Truthe (dir.), Language and automata theory and applications. (p. 221-232). Lecture Notes in Computer Science. Cham, Switzerland : Springer.

[thumbnail of BlondinLapointeTremblay-LATA2016.pdf]
Prévisualisation
PDF - Version acceptée
417kB

URL officielle: http://dx.doi.org/doi:10.1007/978-3-319-30000-9_17

Résumé

In 2014, it was conjectured that any polyomino can be factorized uniquely as a product of prime polyominoes. 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(Z2) 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(Z2). 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.

Type de document:Chapitre de livre
Date:2016
Lieu de publication:Cham, Switzerland
Sujets:Sciences naturelles et génie > Sciences mathématiques
Département, module, service et unité de recherche:Départements et modules > Département d'informatique et de mathématique
Éditeurs:Dediu, Adrian-Horia
Janoušek, Jan
Martín-Vide, Carlos
Truthe, Bianca
Liens connexes:
Mots-clés:Codes, combinatorics on words, graphs, digital geometry, topological graph theory, morphisms
Déposé le:15 déc. 2020 00:09
Dernière modification:15 déc. 2020 23:03
Afficher les statistiques de telechargements

Éditer le document (administrateurs uniquement)

Creative Commons LicenseSauf indication contraire, les documents archivés dans Constellation sont rendus disponibles selon les termes de la licence Creative Commons "Paternité, pas d'utilisation commerciale, pas de modification" 2.5 Canada.

Bibliothèque Paul-Émile-Boulet, UQAC
555, boulevard de l'Université
Chicoutimi (Québec)  CANADA G7H 2B1
418 545-5011, poste 5630