In "Finite Model Theory and Its Applications", page 152, it is said that Deterministic Transitive Closure, on ordered finite structures, captures LOGSPACE.
Hence, taking into account that FOL captures LOGSPACE, the following should be possible:
- Given a functional relation R(X,Y) (e.g. "motherOf(X,Y)")
- Define, in FOL, a predicate T(X,Y) that captures its transitive closure (e.g. "femaleAncestor(X, Y)").
I would like to know how to define such predicate. This would be quite easy in Datalog, using recursion, but it should be possible to define it without recursion, which is the question that puzzles me.