1998 | OriginalPaper | Buchkapitel
A Kleene Iteration for Parallelism
verfasst von : Kamal Lodaya, Pascal Weil
Erschienen in: Foundations of Software Technology and Theoretical Computer Science
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
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
This paper extends automata-theoretic techniques to unbounded parallel behaviour, as seen for instance in Petri nets. Languages are defined to be sets of (labelled) series-parallel posets – or, equivalently, sets of terms in an algebra with two product operations: sequential and parallel. In an earlier paper, we restricted ourselves to languages of posets having bounded width and introduced a notion of branching automaton. In this paper, we drop the restriction to bounded width. We define rational expressions, a natural generalization of the usual ones over words, and prove a Kleene theorem connecting them to regular languages (accepted by finite branching automata). We also show that recognizable languages (inverse images by a morphism into a finite algebra) are strictly weaker.