# PROGRAM’S PETRI-NETS, TREES AND TOPOLOGICAL UNIVERSAL COVERINGS

Costas Kyritsis

Software laboratory,

Department of  Electrical and Computer Engineering

National Technical University  of  Athens

Petros Stefaneas

### 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 (Rogers, 1967). The equivalence of  these three alternative definitions is considered in partial support of the Church’s thesis. More modern approaches relate the concept to the applications in Computational Linguistics, grammars and the work of N. Chomsky. Based on these definitions, the culture of computational algorithmic complexity has been developed (Wagner & Weshsung, 1986), (Horrowitz & Sahni, 1993). Other approaches start with the classical popular concept of flow-chart and develop a definition based on the theory of categories that includes also non-deterministic algorithms (Goguen, 1974). We adapt here Goguen's approach that defines the program through its flow-chart. Flow - charts are conceived as petri-nets, where arrows correspond to the squares   of the petri-net and the vertices to the circles of the petri-net. We switch to petri-nets from (oriented) graphs and vice-versa with the usual convention: Any sequence arrow-square-arrow becomes an arrow and circles become vertices.

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 .