Acyclicity is efficiently recognizable:
Deciding whether a hypergraph is acyclic is feasible in linear time [1]} and
belongs to the class \({\rm L}\)  (deterministic logspace). Indeed, this follows from the fact that hypergraph acyclicity belongs to \(\mbox{\rm SL}\) 
[2]}, and that \(\mbox{\rm SL}\)  is equal to \({\rm L}\)  [3]}.
Acyclic instances can be efficiently solved:
After the bottom-up step described above, one can perform the reverse top-down step
by filtering each child vertex from those tuples that do not match with its parent tuples.
The relations obtained after the top-down step enjoy the global consistency property, i.e.,
they contain only tuples whose values are part of some solution of the CSP.
Then, all solutions can be computed with a backtrack-free
procedure, and thus in total polynomial time, i.e., in time
polynomial in the input plus the output [4]} (and
actually also with polynomial delay). Alternatively, one may enforce pairwise consistency by taking the semijoins between all pairs of relations
until a fixpoint is reached. Indeed, acyclic
instances that fulfil this property also fulfil the global consistency property [5]}.
Acyclic instances are parallelizable:
It has been shown that solving acyclic CSP instances is highly parallelizable, as this problem
(actually, deciding the existence of a solution) is complete for the low complexity class \(\mbox{\rm LOGCFL}\)  [2]}. Efficient
parallel algorithms are discussed in [2]} and [8]}.

