Title: On the Upward/Downward Closures of Petri Nets,
Abstract: We study the size and the complexity of computing finite state automata (FSA)
representing and approximating the downward and the upward closure of Petri net
languages with coverability as the acceptance condition. We show how to
construct an FSA recognizing the upward closure of a Petri net language in
doubly-exponential time, and therefore the size is at most doubly exponential.
For downward closures, we prove that the size of the minimal automata can be
non-primitive recursive. In the case of BPP nets, a well-known subclass of
Petri nets, we show that an FSA accepting the downward/upward closure can be
constructed in exponential time. Furthermore, we consider the problem of
checking whether a simple regular language is included in the downward/upward
closure of a Petri net/BPP net language. We show that this problem is
EXPSPACE-complete (resp. NP-complete) in the case of Petri nets (resp. BPP
nets). Finally, we show that it is decidable whether a Petri net language is
upward/downward closed. To this end, we prove that one can decide whether a
given regular language is a subset of a Petri net coverability language.