Re: Transitive Order of a Relation

On May 9, 4:58 am, quasi <q...@xxxxxxxx> wrote:
On 8 May 2007 19:30:30 -0700, DGo...@xxxxxxxxxxxx wrote:





On May 6, 8:33 am, DGo...@xxxxxxxxxxxx wrote:
Given a relation R, which is a subset of the power set P of the
Cartesian product SxS of a set S with itself, R is either transitive
or it is not. The transitive closure of R is well defined and is
conventionally noted R^t, where t is not an integer, but indicates
"transitive".

Matrix multiplication may be used to find the transitive closure of a
graph. The mth power of an ajacency matrix is the number of paths of
length m between the relevant vertices. Each time the adjacency matrix
A of a graph G of a relation R is squared, new paths of length two may
appear. For large graphs this is easier using computer methods than
looking for potential closures in the graph by inspection. When none
appear, we are done; we have found the transitive closure of the
relation.

By defining 0/0 = 0, we may normalize any power of an adjacency matrix
simply to directly represent the transitive closure of a graph. We may
write (piecewise) (R / |R|) to normalize a matrix if 0/0 = 0. Then,
the transitive order of a relation R is

the minimial power n such the normalized adjacency matrices

(piecewise)
( (R^(2^n)) / | R^(2^n)) | ) = ( (R^(2^(n+1))) / | R^(2^(n+1)))
| ).

The transitive order of a transitive relation is 1.

The transitive closure of a relation with transitive order n is
therefore

( (R^(2^n)) / | R^(2^n)) | ).

Is this known?

Doug Goncz
Replikon Research
Seven Corners, VA 22044-0394

Hello? Is anybody listening?

Doug

Please define the term "relation of transitive order n"

At first glance, it appears you are defining the order of a relation
to be the least positive integer n power such that your sequence of
matrices stabilizes. If so your claim is true by definition -- there's
nothing to prove.

Yes, thank you for replying, quasi.

OK, it's true by definition.

Is it of any use and might a journal article be of interest to others?
Or perhaps a letter to the editor of a journal?

Is there a standard method to find the transitive closure of a
complicated relation, say of order > 10, other than matrix powers.

Doug

.

Relevant Pages

  • Re: Transitive Order of a Relation
    ... The transitive closure of R is well defined and is ... A of a graph G of a relation R is squared, new paths of length two may ... Please define the term "relation of transitive order n" ... Is it a standard terminology? ...
    (sci.math)
  • Re: Can this be done in SQL? Find the transitive relation
    ... I am strugling get the following done in SQL. ... http://www.bookpool.com/sm/0977671542, section on transitive closure ... There are several key graph concepts that would guide your intuition ... Figure 6.5: Reachability as an equivalence relation: graph from fig. ...
    (comp.databases.oracle.server)
  • Transitive Order of a Relation
    ... which is a subset of the power set P of the ... The transitive closure of R is well defined and is ... A of a graph G of a relation R is squared, new paths of length two may ... we may normalize any power of an adjacency matrix ...
    (sci.math)
  • Re: Help needed: Is Quick-Union-Find the right solution to this problem ?
    ... That's a solved problem (checking for cycles in a directed graph using ... > What you want is a "transitive closure" of the graph. ... I did a bit of research and studied two approaches to Warshall ... which is pretty easy to accomplish or I might have an array of strings ...
    (comp.programming)
  • Re: Knowledge in Action (Reiter) - example 2.1.1
    ... Logical Foundations for Specifying and Implementing Dynamical ... transitive closure of a graph, G, and says that the following "naive" ... model of the above naive definition for transitive closure. ...
    (sci.logic)