Anzeige
Erschienen in:
2011 | OriginalPaper | Buchkapitel
Kleene Theorems for Product Systems
verfasst von : Kamal Lodaya, Madhavan Mukund, Ramchandra Phawade
Erschienen in: Descriptional Complexity of Formal Systems
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. 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.