Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
Drexel University or The Math Forum.
|
|
|
|
Re: Reflexive-transitive closure
Posted:
Jul 9, 2012 8:05 AM
|
|
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.
|
|
|
|
