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
Abstract
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
