hi everyone,

i was reading an article by don knuth which showed that given a binary
relation R, there are at most 10 different relations that can be
derived from R using the transitive closure operation (written as R+)
and the complement operation (written as R-).

he showed that you need to define R over a set with at least 5 elements
to meet the bound of 10.  there are similar bound when you introduce
more operators, such as transpose, unioning identity, etc.

i was wondering if anyone know of general decidability results for
simple identities involving relations?

specifically, i thought one path to deciding these knuth-like problems
may be to  prove a finite model theorem, i.e., derive a bound on the
cardinality of the universe from the structure of the parse tree of the
formula in questions – the identity holds iff it holds in all cases
where the relations are defined over sets whose cardinality is the
bound.

cheers,
adnan