**Costas Kyritsis**

Software laboratory,

Department of Electrical and Computer Engineering

** Petros
Stefaneas**

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** (**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 x_{o }be a point
of X. A path in X that begins and ends at x_{o }is called **loop **based at x_{o}. The set of
path homotopy classes of loops based at x_{o, }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 **x_{o }It
is denoted by p_{1}(X,
x_{o}).

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 p_{1}(X,
x_{o}) is the trivial (one-element) group for every x_{o}Î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 p_{1}(V,b)
into p_{1}(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 **

**Definition
5 **

**Theorem
6 ***Let p:E**®**B be
a covering map ; let p(e _{0}) =b_{0 }. Let f and g be two paths
in B from b_{0 }to ; b_{1 }let *

**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
*

**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 *

**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 X_{1
}… X_{n }with X_{1 }= A and X_{2 }=
B and X_{I }is in R relation to X_{I+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 .