<p>What you are looking for with "checking edges" are known as Petri nets with <em>read arcs</em>.  In your question you also mention nets with a single read edge, those are called <em>communication-free</em>.  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, <em>Petri Nets, Commutative Context-Free Grammars, and Basic Parallel Processes</em>, FCT 1995, LNCS 965, pp. 221--232, and <em>Fundamenta Informatica</em> 31(1):13--25, 1997.</p>

CC BY-SA 2.5
2011-04-01T00:41:36.093Z
2011-04-01T09:14:53.737Z
2011-04-01T09:14:53.737Z
Sylvain
<p>Is there a studied model of Petri nets where each transition only has <em>one</em> 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?</p>

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

<p>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.</p>

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

<p>I'm looking for a <em>restricted</em> 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.</p>

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

<p>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.</p>

<p>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).</p>

<p>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$.</p>

CC BY-SA 2.5
2011-03-31T14:14:47.837Z
I wanted to add the tag [petri-nets] but I don't have enough rep to create new tags.
Max
CC BY-SA 2.5
2011-03-31T14:27:38.847Z
@Max: Thank you for suggesting the appropriate tag.  I added it.
Tsuyoshi Ito
CC BY-SA 2.5
2011-03-31T14:29:40.337Z
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.
Dave Clarke
CC BY-SA 2.5
2011-03-31T14:32:20.233Z
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?
Tsuyoshi Ito
CC BY-SA 2.5
2011-03-31T14:35:40.310Z
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.
Tsuyoshi Ito
CC BY-SA 2.5
2011-03-31T14:38:04.463Z
My model is a *restriction* of Petri nets. Of course any property of all Petri nets applies to this case, but I want to know if there are any results on this special case, which I suspect is "easier" than the general Petri nets.
Max
CC BY-SA 2.5
2011-03-31T14:42:15.240Z
For example, AFAICT there is a Petri nets whose reachability set calculates an exponential function in the sense that it includes (0, 0, ..., 0, x) iff x is a power of two, but there is no such Petri net under this restriction.
Max
CC BY-SA 2.5
2011-03-31T15:01:54.540Z
(1) The first paragraph of the question reads “[…] _can_ also have ‘checking’ edges,” which means that checking edges are optional, implying that it is a generalization of the usual Petri nets.  The second paragraph seems to require that each transition has at least one “checking” edge, which contradicts the first paragraph.  (2) The requirement that each transition has at least one checking edge is only superficial in the sense which I explained in the previous comment.
Tsuyoshi Ito
CC BY-SA 2.5
2011-03-31T15:19:35.713Z
Tsuyoshi: the essential part of the first paragraph is "*only* has *one* normal in-edge". The second paragraph says that *all* the in-edges are checking edges, except for at most one.
Max
CC BY-SA 2.5
2011-03-31T15:31:31.093Z
@Max: If I understand your question correctly, you can model this using a Petri net with transition guards.  A fancier version of what I think you are trying to do can be found in [History-Dependent Petri Nets](http://www.google.com/url?sa=t&source=web&cd=3&sqi=2&ved=0CCgQFjAC&url=http%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fdownload%3Fdoi%3D10.1.1.95.4335%26rep%3Drep1%26type%3Dpdf&rct=j&q=petri%20net%20guard&ei=zJ2UTd3_OpKw0QGckO3kCw&usg=AFQjCNF1zjMvoM9HVnArHh-Bdx_K061FLw&cad=rja) by van Hee et al.
Aaron Sterling
CC BY-SA 2.5
2011-03-31T15:38:37.303Z
Aaron: an extension of Petri nets which can simulate the nets I describe is not interesting for me (as I say, my nets can be simulated by an ordinary Petri net). I'm looking for a *smaller* class.
Max
CC BY-SA 2.5
2011-03-31T15:45:46.330Z
I had been overlooking the restriction that each transition can have only one normal incoming edge.  Thanks for correcting me.
Tsuyoshi Ito
<reference-request><fl.formal-languages><petri-nets>
Are there Petri net models with "checking" rather than "taking" transitions?
Max
# Are there Petri net models with "checking" rather than "taking" transitions?

(Asked by: username_0 on 2011-03-31)

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

**Tags:** reference-request, fl.formal-languages, petri-nets

> **Comments:**
> **username_0**: I wanted to add the tag [petri-nets] but I don't have enough rep to create new tags.  
> **username_1**: @username_0: Thank you for suggesting the appropriate tag.  I added it.  
> **username_2**: 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.  
> **username_1**: 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?  
> **username_1**: 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.  
> **username_0**: My model is a *restriction* of Petri nets. Of course any property of all Petri nets applies to this case, but I want to know if there are any results on this special case, which I suspect is "easier" than the general Petri nets.  
> **username_0**: For example, AFAICT there is a Petri nets whose reachability set calculates an exponential function in the sense that it includes (0, 0, ..., 0, x) iff x is a power of two, but there is no such Petri net under this restriction.  
> **username_1**: (1) The first paragraph of the question reads “[…] _can_ also have ‘checking’ edges,” which means that checking edges are optional, implying that it is a generalization of the usual Petri nets.  The second paragraph seems to require that each transition has at least one “checking” edge, which contradicts the first paragraph.  (2) The requirement that each transition has at least one checking edge is only superficial in the sense which I explained in the previous comment.  
> **username_0**: Tsuyoshi: the essential part of the first paragraph is "*only* has *one* normal in-edge". The second paragraph says that *all* the in-edges are checking edges, except for at most one.  
> **username_3**: @username_0: If I understand your question correctly, you can model this using a Petri net with transition guards.  A fancier version of what I think you are trying to do can be found in [History-Dependent Petri Nets](http://www.google.com/url?sa=t&source=web&cd=3&sqi=2&ved=0CCgQFjAC&url=http%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fdownload%3Fdoi%3D10.1.1.95.4335%26rep%3Drep1%26type%3Dpdf&rct=j&q=petri%20net%20guard&ei=zJ2UTd3_OpKw0QGckO3kCw&usg=AFQjCNF1zjMvoM9HVnArHh-Bdx_K061FLw&cad=rja) by van Hee et al.  
> **username_0**: Aaron: an extension of Petri nets which can simulate the nets I describe is not interesting for me (as I say, my nets can be simulated by an ordinary Petri net). I'm looking for a *smaller* class.  
> **username_1**: I had been overlooking the restriction that each transition can have only one normal incoming edge.  Thanks for correcting me.  

---

## 1 answers

### Answer by username_4 on 2011-04-01. Score: 5 | Accepted answer

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.


---

