Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



Re: Reflexivetransitive closure
Posted:
Jul 9, 2012 8:05 AM


Kaba writes:
> The reflexivetransitive 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 > "reflexivetransitive completion" in the sense of iterating a > (setvalued) 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 reflexivetransitive > 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.



