Re: Transitive Closure
Date: Mon, 17 May 2004 15:15:04 +0300
Message-ID: <40a8abfa$1_at_post.usenet.com>
"Mikito Harakiri" <mikharakiri_at_iahu.com> wrote in message
news:cl7pc.22$7Q3.233_at_news.oracle.com...
>
> "x" <x-false_at_yahoo.com> wrote in message
news:40a4f84f$1_at_post.usenet.com...
> > > > Wikipedia says: "...the transitive closure of a binary relation R on
a
> > > > set X is the smallest transitive relation on X that contains R."
> > >
> > > I have better definition. Assume that graph adjacency matrix is A.
Then,
> > > transitive closure is
> > >
> > > (1-A)^(-1) = I + A + A^2 + A^3 + ...
> > >
> > > On the other hand
> > >
> > > exp(A) = I + A +A^2/2 + A^3/6 + ...
> > >
> > > Which one is correct TC definition?
> >
> > What type have the elements of A ?
>
> Elements of A have values 0 and 1. (Although, the adjacency matrix
> definition easily extends to graphs with weighted edges). Elements of
TC(A),
> on the other hand, should be allowed at least Real. TC(A) is interpreted
> back to graph the following way: if matrix component value is non 0 then
> nodes are adjacent.
I asked what type. {0,1} is not a type.
0 , 1, +, ^, / as symbols for what ?
See http://dimacs.rutgers.edu/Workshops/Lattices/slides/kozen.ppt (kleene
algebras, kleene algebras with tests)
RM lacks an iteration operator. This is why Codd spoke about "data
sublanguage".
In my opinion TC on first order binary relations won't fill this hole in RM.
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
- Usenet.com - The #1 Usenet Newsgroup Service on The Planet! *** http://www.usenet.com Unlimited Download - 19 Seperate Servers - 90,000 groups - Uncensored -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=