Period Piece: NEXPTIME-complete problems on digraphs via Boolean network dynamics
The central object in this work is the Boolean network, a function $f:\{0,1\}^V \to \{0,1\}^V$. Often identified with $f$ is its dynamics $D_f$, the digraph with exactly $\{x \to y : f(x)=y\}$ as its arcs. The interaction graph of $f$ is the digraph $G$ on $V$ which can be thought of as representing the dependencies of the components of $f$ on one another. On the other hand, model-checking is a major field of study in graph algorithms and complexity. We consider problems at the intersection of these paradigms: for a given property $φ$, we say that a digraph $G$ is $φ$-dynamic if $G$ is the…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.16561
curl -X POST /api/v1/records/arxiv/2610.16561/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.16561/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'