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

On the arithmetics of discrete figures

Blondin Massé Alexandre, Tall Amadou Makhtar et Tremblay Hugo. (2014). On the arithmetics of discrete figures. Dans Adrian-Horia Dediu, Carlos Martín-Vide, José-Luis Sierra-Rodríguez et Bianca Truthe (dir.), Language and automata theory and applications. (8370, p. 198-209). Lecture Notes in Computer Science. Cham, Switzerland : Springer.

[thumbnail of lata2014-prime.pdf]
Prévisualisation
PDF - Version acceptée
339kB

URL officielle: http://dx.doi.org/doi:10.1007/978-3-319-04921-2_16

Résumé

Discrete figures (or polyominoes) are fundamental objects in combinatorics and discrete geometry, having been studied in many contexts, ranging from game theory to tiling problems. In 2008, Provençal introduced the concept of prime and composed polyominoes, which arises naturally from a composition operator acting on these discrete figures. Our goal is to study further polyomino composition and, in particular, factorization of polyominoes as a product of prime ones. We provide a polynomial time (with respect to the perimeter of the polyomino) algorithm that allows one to compute such a factorization. As a consequence, primality of polyominoes can be decided in polynomial time.

Type de document:Chapitre de livre
Date:2014
Lieu de publication:Cham, Switzerland
Identifiant unique:10.1007/978-3-319-04921-2_16
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
Martín-Vide, Carlos
Sierra-Rodríguez, José-Luis
Truthe, Bianca
Mots-clés:discrete figures, polyominoes, boundary words, primality, tiling, morphism
Déposé le:15 déc. 2020 00:36
Dernière modification:15 déc. 2020 22:55
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