Let a directed graph $G = (V, E)$ be given, plus a constraint map $c: E \rightarrow V$ and a set $T \subseteq V$ of initial token locations. A valid move consists of sliding a token from $v$ to $w$ if:

  • $v \in T$ — to slide a token, it must be there.
  • $w \not \in T$ — to move a token somewhere, the new place must be empty.
  • $c(v, w) \in T$ — (the unusual bit) to use an edge, some token must occupy the "activator" vertex. Note that the trivial constraint $c(v, w) = v$ is allowed.

(Then $T \Rightarrow^1 (T \setminus \{v\}) \cup \{w\}$. An interesting decision problem might be this: given $v$, is there a $T'$ s.t. $T \Rightarrow^* T'$ and $v \in T'$; there are plenty others.)

I think this can be reformulated as a Petri net, with transitions $\{v, c(v, w)\} \rightarrow \{w, c(v, w)\}$ when $c(v, w) \neq v$ and $\{v\} \rightarrow \{w\}$ when $c(v, w) = v$. However, I am very unfamiliar with Petri nets. Does this have some correspondence to Petri nets at all? Is the subtype of Petri nets where all transitions are on the above form well-studied? What are the major results, especially concerning the computational complexity of the most interesting decision and function problems?

  • $\begingroup$ This seems to be a condition/event system with a side-condition. I do not think that side conditions are always appreciated. Alternatively I think these are place/transition/systems where all places have capacity 1. In those P/T systems the side condition seems OK. I do not know any complexity results. Sorry. $\endgroup$ – Hendrik Jan Mar 21 '17 at 19:37
  • $\begingroup$ Thanks for replying. Discussing with a university buddy confirms this to be (equivalent) to a particular kind of Petri net. A paper shows that adding test arcs (eqv. to my condition) does not increase the expressive power of Petri net (nets with test arcs can be rewritten to behaviourally equivalent Petri nets without them, using the transitions in my question). The properties usually studied about petri nets are liveness, deadlock and reachability: given $T'$, does $T \Rightarrow^* T'$, but my question is apparently not studied. $\endgroup$ – Jonas Kölker Mar 22 '17 at 11:35
  • $\begingroup$ I don't know if this is helpful, but token reconfiguration or token swapping are keywords you could try when searching. $\endgroup$ – Juho Mar 24 '17 at 22:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.