3
$\begingroup$

Is there a studied model of Petri nets where each transition only has one normal in-edge (which removes a marker from a place), but can also have "checking" edges, which only check whether there is a marker in a place?

Alternatively, each transition has at least one out-edge to each of its input places, except for one.

Such a net would model a random-permitting context grammar, but a Google Scholar search for "random permitting context" and "petri net" doesn't yield any likely candidates.

EDIT: it seems my question is not very clear, but I'm unsure exactly of how to improve it.

I'm looking for a restricted class of Petri nets: these nets can indeed be simulated by ordinary Petri nets, so I'm definitely not looking for a generalisation of Petri nets.

Unless I'm more-than-usually confused, there are Petri nets which cannot be simulated by these nets.

Perhaps my motivation and what I mean by my definition can be clarified by a further restriction: we keep the restriction of each transition having only one normal in-edge, but further disallow checking edges. In this case, we get a model (the Parikh vectors of) the context-free languages: each transition represents a production and places represent symbols, with a production deleting one symbol and adding any number of others.

Marek and Češka have shown that Petri nets can simulate any random-context language; the random-permitting context languages are a strictly smaller class (even when we ignore the order of symbols). For example $\{a^{2^n} : n \in \mathbb{N}\}$ is a random-context language but is not random-permitting context language (these languages satisfy a pumping lemma).

The Petri nets here correspond to these languages: the production $A \rightarrow XYZ$ with permitting set $\{C,D\}$ corresponds to a transition with an in-edge from $A$, out-edges to $X$, $Y$ and $Z$, and checking edges from $C$ and $D$.

$\endgroup$
  • 1
    $\begingroup$ I wanted to add the tag [petri-nets] but I don't have enough rep to create new tags. $\endgroup$ – Max Mar 31 '11 at 14:14
  • $\begingroup$ @Max: Thank you for suggesting the appropriate tag. I added it. $\endgroup$ – Tsuyoshi Ito Mar 31 '11 at 14:27
  • 1
    $\begingroup$ I don't think it is necessary, as you can have a transition that puts the token back where it came from. There are Petri nets with inhibitor arcs if you want to check that a token is not present. $\endgroup$ – Dave Clarke Mar 31 '11 at 14:29
  • $\begingroup$ The question is unclear to me. As you suggest in the second paragraph, a “checking” edge can be simulated by a pair of a usual incoming edge and a usual outgoing edge, which means that allowing “checking” edges does not change the power of the Petri net model. So what is the difference between the usual model of Petri nets and your model? $\endgroup$ – Tsuyoshi Ito Mar 31 '11 at 14:32
  • $\begingroup$ Do you require that each transition has at least one “checking” incoming edge? This restriction is inessential because we can add a place which always hold one token and superficially “check” existence of a token at this place. $\endgroup$ – Tsuyoshi Ito Mar 31 '11 at 14:35
5
$\begingroup$

What you are looking for with "checking edges" are known as Petri nets with read arcs. In your question you also mention nets with a single read edge, those are called communication-free. It would be difficult (for me) to point to the original author(s) for these notions, but they are fairly standard. Relationships between communication-free Petri nets and Parikh images of context-free languages are investigated for instance by Javier Esparza, Petri Nets, Commutative Context-Free Grammars, and Basic Parallel Processes, FCT 1995, LNCS 965, pp. 221--232, and Fundamenta Informatica 31(1):13--25, 1997.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.