Algorithmic Aspects of Concurrent Automata
Peter H. Deussen · 1998
. Partial order semantics of Petri nets have a long history. In this paper, we describe a formalism which combines partial order semantics with the usual notion of markings of a Petri net. We call this formalism concurrent automata. We present a generation algorithm for concurrent automata. We show that our algorithm is correct in the sense of semi language equivalence: The generated automaton recognizes essentially the same set of semiwords as the associated Petri net. Key words. Concurrent automata, Petri Nets, Partial Order Semantics, Semiwords, Semi Languages. 1. Introduction Partial order semantics of formalisms designed to describe concurrent systems have a long history. Concentrating on Petri nets, instances of those semantics are processes [1], (prime) event structures [11], partial words [6] and semiwords [12, 17], or branching processes [3]. Especially a finite representation of a branching process of a 1-bounded Petri net, called the finite prefix of the maximal branching p...