[Top] [All Lists]

[ontac-forum] Summary of pi calculus and situation calculus

To: ONTAC-WG General Discussion <ontac-forum@xxxxxxxxxxxxxx>
Cc: CG <cg@xxxxxxxxxx>
From: "John F. Sowa" <sowa@xxxxxxxxxxx>
Date: Wed, 11 Jan 2006 12:36:08 -0500
Message-id: <43C54208.6090007@xxxxxxxxxxx>
I accidentally pushed the send button before I had finished
this note.  Following is the basic summary of how these
two methods for reasoning about time and processes are
related to one another and to various special cases that
people have been using for years:    (01)

  1. In the mid 1960s, Carl Adam Petri developed a theory of
     distributed interacting systems, which are now called
     Petri nets.  The basic idea is that each event type is
     represented by a node, called a _transition_, which has
     a set of input conditions, called _places_, and a set
     of output conditions, which are places that may be the
     inputs to other transitions.  Anybody who has ever used
     a PERT chart, flow chart, finite-state machine, or UML
     activity diagram has used a special case of a Petri net.    (02)

  2. Around the same time, John McCarthy developed a theory
     of _situations_, which represent the complete state
     of the universe (or at least the relevant part of the
     universe for the purpose of the given problem) at one
     instant of time.  For each event E, the immediately
     preceding situation is the conjunction of *all* the
     preconditions for E and *all* the conditions (pre or
     post) for every event other than E, whether or not it's
     in any way relevant to E.  After E has occurred, the
     immediately following situation is the conjunction of
     *all* the postconditions for E together with *all*
     the conditions for all other events.    (03)

  3. In effect, Petri nets focus on *local* conditions for
     each event, but situation calculus lumps all conditions
     at each instant of time into a single *global* situation.
     It is possible to transform any Petri net into a situation
     by taking a snapshot of each state of the net at every
     instant of time t and identifying the conjunction of all
     active places at time t with one of McCarthy's situations.
     Going in the opposite direction from a global situation
     to the local conditions is a much more difficult problem.    (04)

  4. For over 30 years, situation calculus has been widely
     used in artificial intelligence, but almost nobody outside
     of AI uses it.  The major difficulty is the so-called
     _frame problem_, which consists of identifying the open
     ended number of conditions that are *not* affected by
     any given event.  Most so-called "solutions" to the frame
     problem are, in effect, ad hoc constructions of the Petri
     net equivalent to the given collection of event types.    (05)

  5. Although Petri nets (and their special cases) are very
     useful for many purposes, they have one major drawback:
     they have a fixed network of event types and conditions.
     In modern telephony networks, new connections of nodes
     are constantly being created and destroyed dynamically.
     To handle such problems, Robin Milner, who was a consultant
     to both ATT and British Telephone, invented the pi calculus.    (06)

  6. The notation for pi calculus is still in flux and many
     different versions have been used.  But the simplest way
     to think about it is to imagine a Petri net (or UML activity
     diagram) in which new nodes and arcs can be created or
     destroyed dynamically.    (07)

In summary, Petri nets are a generalization of situation calculus
in which the global situations are split into a set of simple
conditions (called places) and each event type is linked to just
the relevant preconditions and postconditions.  Pi calculus is
a dynamic generalization of Petri nets in which conditions,
events, and _ports_ between them can be created or destroyed
dynamically.    (08)

Since there are so many different variations of pi calculus
(including situation calculus, which is just one very limited
special case of pi calculus), I do *not* recommend that any
version be put into the core (or even a hub) of the ontology.
But I do recommend that *all* of them be made available at
the problem-oriented level.    (09)

John Sowa    (010)

Message Archives: http://colab.cim3.net/forum/ontac-forum/
To Post: mailto:ontac-forum@xxxxxxxxxxxxxx
Shared Files: http://colab.cim3.net/file/work/SICoP/ontac/
Community Wiki: 
http://colab.cim3.net/cgi-bin/wiki.pl?SICoP/OntologyTaxonomyCoordinatingWG    (011)
<Prev in Thread] Current Thread [Next in Thread>