Hot answers tagged

1

Partial answer only. For me, the paper is behind a paywall. So I can base this only on its abstract and your question. I believe you have a point with your complexity doubts. I can see how to write an FO[LFP] self-interpreter, provided there is a way to handle large arities. In particular, the self-interpreter has a single, fixed, maximum arity and number ...


1

I don't think you can do it in plain Datalog, but you can do it in Datalog plus negation. I suggest you define a relation $R$, so that $R(x,y)$ is true if vertex $y$ is reachable from vertex $x$ in one or more steps. You can define $R$ recursively, namely, $$R(x,y) = E(x,y) \lor \exists w . E(x,w) \land R(w,y),$$ where $E$ is a relation that represents ...


1

There was a misunderstanding in regards to the evaluation algorithm/minimal model. The derivation of new values is atomic e.g.: step 1: p = {} q = {} step 2: p = r q = r In step 2 p and q only see the value that each other had at step 1(the old value). I thought p and q would have access to the value of the current step and thus, the order of ...


Only top voted, non community-wiki answers of a minimum length are eligible