Kleene Theorems for Product Systems

Lodaya, Kamal ; Mukund, Madhavan ; Phawade, Ramchandra (2011) Kleene Theorems for Product Systems In: 2011 International Conference on Descriptional Complexity of Formal Systems, 25-27 Jul 2011, Gießen near Limburg, Germany.

Full text not available from this repository.

Official URL: https://link.springer.com/chapter/10.1007/978-3-64...

Related URL: http://dx.doi.org/10.1007/978-3-642-22600-7_19


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.

Item Type:Conference or Workshop Item (Paper)
Source:Copyright of this article belongs to Springer-Verlag.
Keywords:Product System; Polynomial Time; Regular Expression; Polynomial Time Algorithm; Free Choice
ID Code:114139
Deposited On:25 May 2018 04:55
Last Modified:25 May 2018 04:55

Repository Staff Only: item control page