Home » forums » LtU Forum

Nets: Petri vs Lafont

I am currently playing with an idea of a PL based on Petri nets (place/transition nets) augmented with Prolog-like unification.
It just occurred to me that though PNs may be cognitively good for many developers (they express static topology of the system explicitly), Interaction nets may be more suitable for expressing some dynamic features.
I was trying to find any papers on relationship between Petri nets and Interaction nets, but found only indirect link through linear logic.
Is anyone aware of theoretical possibilities to (bi)simulate PNs with INs?
Or any other result about their comparative expressiveness?

By Andris Birkmanis at 2004-06-29 09:25 | LtU Forum | previous forum topic | next forum topic | other blogs | 9620 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Introduction to Interaction Nets

BTW, a good resource on Interaction nets is Interaction Combinators. Unfortunately, the only online copy of the original Lafont paper from 1990 I was able to find is located at ACM, and is protected :-(

So far the (intuitive) differences between PNs and INs I see are:
Strong confluence property in INs (intuitively: no matter what you choose to do, you not only arrive to the same result, but also by taking the same actions).

PS: I appear to be unable to edit my original post, is this by design?

By Andris Birkmanis at Tue, 2004-06-29 09:39 | login or register to post comments

Editing posts

Also, I appear to be unable to edit my previous post, is this by design?

No. We are investigating.

By Ehud Lamm at Tue, 2004-06-29 09:47 | login or register to post comments

Port Graph Grammars

The observation that Petri nets are non-confluent and INs are confluent is a killer for the possibility of good representations of PNs by INs, but if you drop the requirement of principality on INs, you get an older non-confluent formalism due to Alan Bawden called Connection Graphs (CG), which is able to naturally represent PNs.

I wrote a paper "Reducibility between classes of port graph grammar", published in the JCSS a couple of years back, that introduced a family of IN-like grammars, which I called port graph grammars; I also wrote a technical report [PS] that covers a lot of the same ground (60pp but most of it is a tricky proof). These papers also discuss a bit of the history of the formalisms and their relevance to programming languages (I strongly recommend Alan Bawden's PhD thesis [PS] also, which is one of the best PhD theses I have ever read). Although I'd worked out the details of the translation from PN to CGs back then, I didn't write it up, but I can explain the details if you are interested.

By Charles A Stewart at Tue, 2004-06-29 10:50 | login or register to post comments

Bawden's thesis

There's an older topic on it -- I liked that thesis a lot, too; it's curious I haven't seen much followup work.

By Darius Bacon at Wed, 2004-06-30 09:40 | login or register to post comments

Graph rewriting on top of SQL

Thanks, yesterday I read both papers (yours and Alan's). They both are very interesting and relevant to what I'm doing.
One stumbles upon a trade-off, though - you get either the expressiveness of more general formalisms or the nice guarantees of less general ones. I don't think I would be able to get through all the horrors of PGGs without understanding Interaction nets first :-)

I have one practical problem with graph-rewritings, which I didn't have with Petri nets - I still don't see an efficient and natural mapping of graphs to relational DBs (don't shout at me :-) ). With PNs, I could just have a table per place, and each transition would have a SQL "select" based on all incoming arcs, "insert"s for each of outgoing arcs, and "delete"s for each of incoming arcs (all of them sharing one DB transaction). In fact, all of these statements would alse share some variables through unification.
I know that this is getting a bit away from PL design, but we have to stay down to earth time to time :-)

Oh, by the way, is it just me, or are graph-rewriting systems indeed very friendly to capability-based security?

By Andris Birkmanis at Wed, 2004-06-30 10:46 | login or register to post comments

It pays to learn

Shame on me, the thing I was so proud to come up with turned out to be widely known as Predicate/Transition Nets - the first kind of high-level Petri nets to be invented :-(

But nothing goes to waste - at least I learned relationships between SQL and Prolog in the hard way :-)

By Andris Birkmanis at Wed, 2004-06-30 19:25 | login or register to post comments

Where to find your papers?

I am interested in reading your papers but linearity.org seem to be down.

Are they available anywhere else?

Is the linearity.org project still going on?

By titto assini at Tue, 2007-09-25 14:52 | login or register to post comments

Why didn't I think of this when the topic came up first?

Andris, you are almost certain to be interested in the work of Satoshi Matsuoka on additive interaction nets. Have a look at Additive Interaction Nets as a Component-Based Programming Language. The basic idea is to add logic variables (ie. a form of non-locality) to interaction nets. Unsurprisingly, this breaks confluence, but a simple syntactic restores it, and the resulting system is quite closely realted to MALL (multiplicative/additive linear logic, ie. without exponentials). This is an underappreciated work. Like Alan Bawden's really; maybe there's a curse on nonstandard variants of Lafont's formalism.

I';d love to hear how your ideas have been progressing.

By Charles A Stewart at Fri, 2005-02-11 04:23 | login or register to post comments

Thanks!

I will have to return to that topic in future, as currently my job responsibilities drove me in the direction of join calculus and friends.

By Andris Birkmanis at Fri, 2005-02-11 07:58 | login or register to post comments