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, it should be possible to:
- Given a functional relation R(X,Y) (e.g. "motherOf(X,Y)")
- It should be possible to 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.