Advertisement
Published in:
2011 | OriginalPaper | Chapter
Kleene Theorems for Product Systems
Authors : Kamal Lodaya, Madhavan Mukund, Ramchandra Phawade
Published in: Descriptional Complexity of Formal Systems
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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.