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