K Lodaya, M Mukund and R Phawade
Proc. DCFS 2011, Springer LNCS 6808 (2011) 235-247.
© Springer-Verlag Berlin Heidelberg
We prove Kleene theorems for two subclasses of labelled product systems which are inspired from well-studied subclasses of 1-bounded Petri nets. For product T-systems 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 structural cyclicity, 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.