Full Page
PROGRAM’S
PETRI-NETS, TREES AND TOPOLOGICAL UNIVERSAL COVERINGS
Costas Kyritsis
Software laboratory,
Department of Electrical and Computer Engineering
Petros
Stefaneas
National Technical University Athens
ABSTRACT
Petri
Nets are frequently used in computing often as alternatives to flow-charts. In
this paper we focus on the relationship among Petri Nets and trees. Using
results from topology we conclude that any connected Petri Net is the quotient
of a tree order.
Key
Words: Trees,Topology,Petri
Nets,Universal Covering Spaces,Program’s Flowcharts.
1. Program’s Petri-nets
The concept of algorithm has a long story. Many different
definitions have been given like that of normal Markov algorithm (Markov, 1961), or Turing machines (Turing, 1936/7), (Eilenberg, 1973) or recursive functions (
2.
Some definitions from topology
In this paragraph we reproduce some results and
definitions from topology as a necessary introduction to the main results of
the paper. We follow closely the book of
Munkres, (1975).
Given a topological space X, a path in X from x to y is a continuous map f:[a,b] ®X of some closed
real interval into X ,such that f(a)=x and f(b)=y. A space X is said to
be path connected if every pair of
points of X can be joined by a path in X. If f is a path in X from x to y, and
g is a path in X from y to z we define the composition f*g of f and g to be the
path h given by the equations:
h(s) = f(2s), for sÎ[0,1/2] and h(s) =
g(2s-1) for sÎ[1/2, 1]
Definition
1 Let X be a topological space, let xo be a point
of X. A path in X that begins and ends at xo is called loop based at xo. The set of
path homotopy classes of loops based at xo, with the operation * (of composition of
representatives of homotopic classes
paths, [f]*[g] = [f*g] ), is called the fundamental group (or first homotopy group ) of X relative to the base point xo It
is denoted by p1(X,
xo).
For a detailed definition of the fundamental
group see again the same book Munkress, (1975). A homotopy transformation of a path
is a continuous transformation of it that fixes the end points and is realizable
in a continuous way inside the topological space.
Definition 2 A space X is said to be simply
connected if it is path-connected space (that is any two points can be connected with a
continuous path ) and if p1(X,
xo) is the trivial (one-element) group for every xoÎX .
A topological space B is said to be semilocally path connected if every
point b of B has a neighborhood V such that the homomorphism of p1(V,b)
into p1(B,b)
induced by inclusion is trivial.
A topological space B is said to be locally
path connected at x if for
every neighbourhood U of x , there is a path-connected neighbourhood V of x
contained in U .If B is locally path
connected at each of its points ,then it is said to be locally path connected.
Definition
3 Let p: E®B be a continuous surjective map. The open set U
of B is said to be evenly covered by
p if the inverse image p-1 (U) can be written as the union of
disjoint open sets Vá in E such that for each á , the
restricion of p to Vá onto U is an homeomorphism. The collection { Vá
} will be called a partition of p-1 (U) into slices. If any point b of B has a
neighbourhood U that is evenly covered by p ,then p is called a covering
map, and E is said to be a covering space of B. If E is a simply
connected space and p is a covering map ,then we say that E is a universal covering space of B .
If B has a universal covering space E, then E is
uniquely determined up to homeomorphism (provided B is locally path connected
). The reason we call E universal
covering space is because it covers every other path-connected covering
space of B. Munkress, (1975).
A sufficient condition for the existence of
universal covering space is given by the
next theorem Munkress, (1975).
Theorem
4 Let B be path connected, locally
path connected, and semilocally simply connected .Let b0 ÎB .Given a subgroup H of p1(B,b0) ,there exists
a path connected covering space p:E®B and
a point e0 Î p-1
(b0) such that the induced homomorphism p* of the
fundamental groups by the covering map ,gives p* ( p1(B,b0))=H .In
particular B has a universal covering space(H={1}).
Definition
5 Let p: E®B be a map. If f
is a continuous mapping of some space X into B , a lifting of f is a map 
:X®E
such that p°=f .
Theorem
6 Let p:E®B be
a covering map ; let p(e0) =b0 . Let f and g be two paths
in B from b0 to ; b1 let 
and 
be their
liftings to paths in E begining at e0
. If f and g are homotopic, then and end at
the same point of E and are homotopic .
3.
The realization of a petri-tree as a topological space.
We try to make formal an intuitive fact of which
are aware many workers in the software engineering that «Any
flow-graph or chart or petri-net of a terminable program can be finally
unfolded to a tree». It seems that there is more than
one approach to this. One is purely algebraic and associates flow-charts to
groups and makes use of the fact that any group is the quotient of a free
group. The other is purely topological .
We chose here the topological one and we follow Serre , (1980).
Definition
7 An non-oriented tree
is a non-oriented graph without circles (or loops). A disjoint union of
non-oriented trees is called non-oriented forest.
Definition
8 Let a non - oriented
graph G with vertices X=vertG and edges Y=edgeG. That is we form the
topological space T which is the disjoint union of X and Yx[0,1], where X and Y
are provided with the discrete topology and the [0,1] has the topology of the
real interval .Let R be the equivalence relation on T for which (y,t)= (
, 1-t) ,(y,1)=t(y) for y in Y and t in [0,1]. By is denoted
the edge y with the inverse direction. The quotient space real(G)=T/R is called
the
(topological) realization of the graph G.
Remark 9 Realization is a functor that commutes with direct limits.
Let a connected graph G. It is not difficult to
prove that real(G) is path connected,
locally path connected and semilocally simply connected topological space.
Lemma
10 Let a connected graph G. This in particular means that any
two vertices can be joint with a path (sequence of
consecutive arrows ) It holds that
real(G) is path connected,
locally path connected and semilocally simply connected topological space.
Corollary
11 The realization real(G) of any connected non-oriented graph G has a
universal covering space which is the realization real(T) of a non-oriented
tree T. The realization real(G) of
any non-oriented graph G has a universal covering space which is the
realization real(T) of a non-oriented set of trees T.
4.
Trees as universal covering topological spaces of graphs.
We continue with the relation of trees and
topological universal coverings.
Definition
12 A morphism of non-oriented graphs from, to H such that the
induced continuous map on the realization of the graphs is also a topological
covering map is called covering map
of the graphs. The graph T is said to cover the
graph H or that the T is a covering graph of H.
Definition
13 The non-oriented tree T of a connected
non-oriented graph G defined by the
universal covering space of real(G) we
call universal covering tree of the graph.
If
the graph is not connected then we apply the above procedure to each one of its
connected components and the graph T is the disjoint union of non-oriened trees
in other words the universal covering
forest of the graph G.
Theorem
14 A universal covering tree of a graph G, covers any other
covering graph of G.
Remark
15 The flow-charts of
programs are finite connected graphs
with two pointed vertices called the beginning and the end and with all their
branches being oriented. If any loop of the graph is walked say only once then
any maximal path (of monotone orientation) has as the first vertice the beginning and as the last the
end. In particular any arrow (oriented branch) is contained in such a path. We
shall call such graphs program’s flow-chart
graphs. If to any arrow is drawn say a square in the middle of it while to
every vertice a circle then it may very well be called program flow petri-net.
The quotient of a
relation relative to an equivalence relation is a relation on the equivalence
classes of the equivalence relation that is “compatible” with the initial
relation. Compatibility usually means that the same type of relation (e.g.
order) appears on the equivalence classes inherited from the initial relation
(the relation holds to representatives of the equivalence classes and does not
depend on the representatives .The image of a universal covering mapping is a
quotient in the relations of incidence of the graphs.
Theorem 16 Any petri-net is the quotient of a petri-tree
Finally we remark that any morphism of graphs f:
G®H defines
a continuous function
in the obvious way (the correspondence of two
branches defines an homeomorphism of
two real open intervals ). We call the
mapping 
the topological morphism extracted by the graph
morphism.
Definition
17 An (oriented ) tree T is a graph such that its
corresponding non-oriented graph is a is a non-oriented tree .An (oriented) forest is the disjoint union of a set
of (oriented) trees .
Remark 18 The algebraic technique to lift or
«untie» program flow-chart graphs to trees corresponds any program flow-chart
graph to a ring- polynomial. We call this
correspondence path generated function. The ring polynomial to which each graph is lifted in the free
ring the polynomial of program flow-chart graph corresponds to a tree that we
call the computation tree of the
corresponding program flow-chart graph.
5. The program’s petri-nets as tangled tree orders .
As any petri-net is the
quotient of tree we analyze trees in relation to order. Trees are then
antisymmetric relations. The relation is simply the precedence of vertices from the next vertices (in direction
from a root to the leaves of the tree if it is finite). The transitive closure
of any antisymmetric relation is well known that is an order relation . These
orders are called tree orders
(Schreider, 1975).
The transitive closure
of a relation R denoted by is defined as
new binary relation such that A is related to B if there is a finite sequence X1
… Xn with X1 = A and X2 =
B and XI is in R relation to XI+1 Thus
any connected petri-net can be derived as quotient of a tree order.
Theorem 19 Any
connected petri-net is the quotient of a tree order
Bibliography.
Eilenberg, S. (1973) Automata, Languages and Machines,
Academic Press. N.York 1973
Gratzer, G. (1979) Universal
Algebra, Springer 1979
Goguen, J.A. (1974) On Homomorphisms, Correctness, Termination,
Unfoldments, and Equivalence of Flow Diagram Programs. Journal of Computer
and System Sciences, Vol 8, No 3, June 1974 pp333-365
Horrowitz, E.- Sahni, S.
(1993) Computer algorithms. Galgotia Pub. 1993
MacLane, S. (1971) Categories
for the working mathematician, Springer
1971
Markov, A.A. (1961) Theory of Algorithms, Jerusalem 1961
Munkress, J.R. (1975) Topology
a first course, Prentice Hall 1975
Musa, J., Iannino A.
& Okumoto K. (1987) Software
Reliability, McGraw Hill 1987
Reisig, W. A
primer in Petri Net Design, Springer
Rogers, H. Theory of recursive functions and effective
Computability, Mc Graw Hill N.York 1967
Serre, J.-P. (1980) Trees, Springer 1980
Shreider, J.A. (1975) Equality, Resemblance and Order. Mir
Publishers Moscow 1975
Shooman, M.L.(1983) Software Engineering McGraw Hill 1983
Turing,
A.M. (1936/37) On Computable numbers,
with an Application to the
Entscheidungsproblem, Proc.Lond.Math. 230-265 (1936/37) Vol.(2) ,42
Wagner, K. & Weshsung, G. (1986) Computational Complexity,
D.Reidel Publishing Company 1986 .