4
$\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$.

Improve this question
$\endgroup$
12
  • 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, 2011 at 14:14
  • $\begingroup$ @Max: Thank you for suggesting the appropriate tag. I added it. $\endgroup$
    – Tsuyoshi Ito
    Mar 31, 2011 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, 2011 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, 2011 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, 2011 at 14:35

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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