On the complexity of the sequential flow problem

A flow system over a finite set Q of states is given by a finite set C of actions, which are directed graphs over Q with arcs labelled by capacities, that is, either a non-negative number or ∞. When the controller plays an given action, any number of token which is in q and below the capacity of an arc from q to q’ may be moved to q’. The sequential flow problem (SFP) is a control problem in such a system which considers arbitrary number of tokens: is it the case that for any number n of tokens in a designated source state s, the controller may find a sequence of actions that leads all tokens to a designated target state t? The SFP was introduced in the context of stochastic control problems of arbitrary numbers of agents, and its complexity remains open. In this talk, I will present an existing EXPSPACE algorithm, and present ongoing work towards a PSPACE upper bound. This is the result of joint ongoing works with Thomas Colcombet, Nathanaël Fijalkow, Mahsa Shirmohammadi and Arnaud Sangnier.

Authors

• Pierre Ohlmann

Keywords

No keywords are indexed for this paper.