[Prev][Next][Index][Thread]
proofnets/graph theory (retore)
Date: Thu, 4 Jun 92 13:57:18 -0700
To: linear@cs.stanford.edu
I have proved an abstract graph theoretical
result which has the following straight forward corollaries:
the splitting times property even with the mix-rule.
(a la Girard sequentialization, even with mix)
the splitting par property
(a la Danos sequentialization)
So this unifies some hitherto unrelated results.
It says a bit more when working with mix.
Assume all conclusion are times. Then for any of
this times conclusions there exists a splitting times and a
feasible path leading to this splitting times.
Also: assume t is a splitting times, with other splitting times
on his right; then there exists among them at least one which is
connected by a feasible path to t.
The combinatorial argument consist in studying agregates of
complete bipartite graphs, ie edge coloured graph such that
each colour is a complete bipartite graph, and direct paths, ie paths
using at most one edge of each colour.
A paper has been written, and his to be submitted
(when polished )to a combinatorics journal.
Christian Retore.
Departement de Mathematiques.
Faculte des Sciences.
Universite d'Angers.
2 Boulevard Lavoisier.
49045 ANGERS cedex
deptang@cicb.fr (collective mailbox)
retore@logique.jussieu.fr