Re: A proposal for entailment tests

> The requirement to check for graph isomorphism in order to determine
> equality sounds just horrible! A simple implementation (which, due to
> lazyness may be favored by many developers) might require O(N!)
> operations in the number of bNodes. This is prohibitive even for N=15
> bNodes in the two graphs.
>
> Wrt above, two questions:
>
> 1. Do we really need bNodes? (I am still missing a convincing argument
> given the added complexity in MT and implementations. Any pointers?)

yes

> 2. As far as I remember, RDF/XML serialization does not allow cycles
> made entirely of bNodes. In this case, only tree isomorphism is
> required, which is logspace (easier than polynomial). Would this be an
> option?

I think it is that what we are doing in our current implementation.
We do tests with 100K bNodes in the order of seconds.

--
Jos