Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.


Math Forum » Discussions » sci.math.* » sci.math

Topic: Reflexive-transitive closure
Replies: 4   Last Post: Jul 12, 2012 10:09 AM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Jussi Piitulainen

Posts: 319
Registered: 12/12/04
Re: Reflexive-transitive closure
Posted: Jul 9, 2012 8:05 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

Kaba writes:

> The reflexive-transitive closure of a relation R subset V^2 is the
> intersection of all those relations in V which are reflexive and
> transitive (at the same time).


Of those reflexive and transitive relations that contain R.

> I am reading a paper in parsing (algorithms to deduce the formal
> grammar structure of a sentence in a formal language induced by a
> formal grammar). In the paper the author uses the term
> "reflexive-transitive completion" in the sense of iterating a
> (set-valued) function:
>
> f^*(x) = union_{i = 0}^inf f^i(x).


I don't see any problem. I take it f^i is V -> V and f^* is V -> P(V)
for some set of values V, but f^* can also be thought of as a relation
in V, and then it is indeed reflexive and transitive.

> It seems to me that the author is simply confused on the meaning of
> the term. This is similar to the Kleene star given by
>
> L^* = union_{k = 0}^inf L^k
>
> for formal languages, but I wouldn't call that reflexive-transitive
> closure either. Have you seen the term used in such contexts?


Kleene star is concatenative closure. Regular aka rational relations
over some alphabet can be both concatenated and composed. Their Kleene
closure is rational by definition; their transitive closure need not
be. The notation R^k for both iterated concatenation and iterated
composition clashes awkwardly when both make sense.

I think we computed transitive closures of finite relations in a set
by iteration until no new pairs appeared in some course I took ages
ago, much like f^* above. I'd expect it to be standard.



Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.