We prove Kleene theorems for two subclasses of labelled product systems which are inspired from well-studied subclasses of 1-bounded Petri nets. For
we define a corresponding class of expressions. The algorithms from systems to expressions and in the reverse direction are both polynomial time. For
product free choice systems
with a restriction of
, that is, the initial global state is a feedback vertex set, going from systems to expressions is still polynomial time; in the reverse direction it is polynomial time with access to an NP oracle for finding deadlocks.