{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreih4242n66uicmvczp6zrv5pk2rhownjyhgmo56yzwk3ben4hkawaa",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mjqijzg3kvh2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2604.15177v1",
  "publishedAt": "2026-04-17T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Enrico Formenti",
    "Eric Goles",
    "Kévin Perrot",
    "Martín Ríos-Wilson",
    "Domingo Ruiz-Tala"
  ],
  "textContent": "**Authors:** Enrico Formenti, Eric Goles, Kévin Perrot, Martín Ríos-Wilson, Domingo Ruiz-Tala\n\nFungal automata are a nature-inspired computational model, where a rule is alternatively applied verticaly and horizontaly. In this work we study the computational complexity of predicting the dynamics of all fungal freezing totalistic one-dimentional rules of radius $1$, exhibiting various behaviors. Despite efficiently predictable in most cases (with non-deterministic logspace algorithms), a non-linear rule is left open to characterize. We further explore the freezing majority rule (which is totalistic), and prove that at radius $1.5$ it becomes $\\mathbf{P}$-complete to predict.",
  "title": "Complexity of Fungal Automaton Prediction"
}