1
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ What do you mean by "data size"? What data are you referring to? $\endgroup$
    – D.W. ♦
    Nov 1 '20 at 20:33
  • $\begingroup$ I mean the size of the database where the query is applied on. I am not referring to any particular domain of data (in excepcion of paragraph two, where I refer to the specific case where the database stores words) $\endgroup$
    – 441Juggler
    Nov 1 '20 at 22:22
  • $\begingroup$ Can you give a self-contained specification of the problem whose space complexity you want to understand? It's not clear to me what a "boolean first-order query solver" means in this context. Please specify the inputs to the algorithm and the desired output. $\endgroup$
    – D.W. ♦
    Nov 1 '20 at 23:30

Your Answer

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

Browse other questions tagged or ask your own question.