Drainability and Fillability of Polyominoes in Diverse Models of Global Control
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910917293244416 |
|---|---|
| author | Fekete, Sándor P. Kramer, Peter Reinhardt, Jan-Marc Rieck, Christian Scheffer, Christian |
| author_facet | Fekete, Sándor P. Kramer, Peter Reinhardt, Jan-Marc Rieck, Christian Scheffer, Christian |
| contents | Tilt models offer intuitive and clean definitions of complex systems in which particles are influenced by global control commands. Despite a wide range of applications, there has been almost no theoretical investigation into the associated issues of filling and draining geometric environments. This is partly because a globally controlled system (i.e., passive matter) exhibits highly complex behavior that cannot be locally restricted. Thus, there is a strong need for theoretical studies that investigate these models both (1) in terms of relative power to each other, and (2) from a complexity theory perspective. In this work, we provide (1) general tools for comparing and contrasting different models of global control, and (2) both complexity and algorithmic results on filling and draining. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_16762 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Drainability and Fillability of Polyominoes in Diverse Models of Global Control Fekete, Sándor P. Kramer, Peter Reinhardt, Jan-Marc Rieck, Christian Scheffer, Christian Computational Geometry F.2.2 Tilt models offer intuitive and clean definitions of complex systems in which particles are influenced by global control commands. Despite a wide range of applications, there has been almost no theoretical investigation into the associated issues of filling and draining geometric environments. This is partly because a globally controlled system (i.e., passive matter) exhibits highly complex behavior that cannot be locally restricted. Thus, there is a strong need for theoretical studies that investigate these models both (1) in terms of relative power to each other, and (2) from a complexity theory perspective. In this work, we provide (1) general tools for comparing and contrasting different models of global control, and (2) both complexity and algorithmic results on filling and draining. |
| title | Drainability and Fillability of Polyominoes in Diverse Models of Global Control |
| topic | Computational Geometry F.2.2 |
| url | https://arxiv.org/abs/2504.16762 |