3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Directed reachability is complete for nondeterministic logspace. $\endgroup$ – Yuval Filmus Sep 6 at 6:58
  • $\begingroup$ @YuvalFilmus, indeed, FOL+TC is complete for nondeterministic logspace, however, I am not speaking about general TC, but deterministic TC. E.g., computing the transitive closure of a non-deterministic relation (such as "parentOf") is NLOGSPACE, but the transitive closure of a deterministic one (such as "motherOf") is LOGSPACE. $\endgroup$ – 441Juggler Sep 6 at 10:48
3
$\begingroup$

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)")

Actually this is not correct: first-order logic does not capture logspace. As you said earlier in your question, FOL plus deterministic transitive closure captures logspace, that is $$ \text{FO(DTC)} = \text{L} $$ but $$ \text{FO} \ne \text{FO(DTC)}, $$

i.e. deterministic transitive closure is not definable in first-order logic.

More generally, FOL is quite limited. FOL captures a class called uniform $\text{AC0}$ (see the complexity zoo and Immerman's diagram); it is the class of queries computable in "constant parallel time". And transitive closure, even deterministic transitive closure, cannot be done in $\text{AC0}$ (with a circuit of constant depth). Even something very simple, calculating the parity of the number of input bits, can't be done in $\text{AC0}$.

How to describe Deterministic Transitive Closure in FOL?

To reiterate: it is impossible.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.