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.
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 |
Éditer le document (administrateurs uniquement)
Altmetric
Altmetric