2026-08-15T23:35:47Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23451 2025-10-10T08:56:40Z ddc:004 open_access

Drainability and Fillability of Polyominoes in Diverse Models of Global Control Fekete, Sándor P. Kramer, Peter Reinhardt, Jan-Marc Rieck, Christian Scheffer, Christian Global control full Tilt single Tilt Fillability Drainability Polyominoes Complexity 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sándor P. Fekete and Peter Kramer and Jan-Marc Reinhardt and Christian Rieck and Christian Scheffer 2025 Is Part Of LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2025.74 urn:nbn:de:0030-drops-234518 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.74 eng https://creativecommons.org/licenses/by/4.0/legalcode