I have the intuitition that, if we implement a (space-efficient) boolean first-order query solver, the amount of consumed memory should depend on the data size (i.e., it should not be constant).
However, in the very specific case of word-structures, I have read that regular expressions captures Monadic Second Order Logics, and hence, first-order queries. Furthermore, regular expressions can be transformed into DFA, which can be further implemented in an algorithm whose memory consumption does not depend on the size of the input. Hence, if my argument is correct, at least in the very specific case of word-structures, the amount of memory consumed for a (space-efficient) first-order query solver should be constant.
Is the space-complexity of solving a boolean first-order query contant (w.r.t. data complexity) only for the case of word-structures? Or is this the general case?
I know that the data-complexity of a first-order query is AC^0, however, I do not know how to relate circuit complexity with space-complexity.