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
Subscribe/Unsubscribe/Config:
http://colab.cim3.net/mailman/listinfo/ontac-forum/
Shared Files: http://colab.cim3.net/file/work/SICoP/ontac/
Community Wiki:
http://colab.cim3.net/cgi-bin/wiki.pl?SICoP/OntologyTaxonomyCoordinatingWG (011)
|