In: Proc. 3-rd Int. Conf. on Developments in Language Theory, Thessaloniki, Greece, pages 461-476. 1997.
Also in: Fundamenta Informaticae, Volume 32, Issue 3-4, pages 373-392. IOS Press, December 1997.
Abstract: A jumping Petri net (JPN) is a net which can spontaneously jump from a marking to another one. It was shown that the reachability problem for JPNs is undecidable, but it is decidable for finite JPNs. This paper establishes some specific properties and investigates the computational power of such nets via the interleaving semantics. It is shown that non-labeled JPNs have the same computational power as labeled JPNs or lambda-labeled JPNS. When final markings are considered, the power of JPNs is equal to the power of Turing machines. Languages generated by finite JPNs can be represented in terms of regular languages and substitutions with classical Petri net languages. A pumping lemma for nonterminal jumping net languages is also established. A connection between finite JPNs and a subclass of inhibitor nets is presented.
Keywords: Petri net languages, interleaving semantics, jumping Petri nets.