14

In relational algebra, we shall first provide an informal definition of left (outer) join, and proceed to prove that it, renaming, selection, join and projection can construct difference, as well as that difference, selection and union can be used to construct left (outer) join. Actually, we'll end up doing it in the reverse order: we'll show how to ...


13

Any form of recursion or iteration in programming is actually a fixed point. For instance, a while loop is characterized by the equation while b do c done ≡ if b then (c ; while b do c done) which is to say that while b do c done is a solution W of the equation W ≡ Φ(W) where Φ(x) ≡ if b then (c ; x). But what if Φ has many fixed points? Which one ...


6

Here is the intuition: least fixed points help you analyze loops. Program analysis involves executing the program -- but abstracting away some details of the data. This is all good. The abstraction helps the analysis go faster than actually running the program, because it allows you to ignore aspects you don't care about. For instance, that's how ...


5

As for your main question, I recommend this short survey by Martin Grohe. Are the queries that are needed in practice usually simple enough that there is no need for a stronger language? I'd say this holds most of the time, given the fair amount of extensions added to common query languages (transitive closure, arithmetic operators, counting, etc.). This ...


5

I'm a bit late, but the only answer does not address the question. You state that the vocabulary $\sigma$ depends on the choice of turing machine $M$. If this were the case, then indeed the claim would only follow for arbitrary vocabularies. But - as the index of $\Phi_M$ and the missing one of $\sigma$ hint at - only the formula depends on $M$, the ...


4

They perform a reduction: given an arbitrary Turing machine, they construct a specific formula equivalent to the question "Does this machine halt on $\varepsilon$?". If validity could be decided in the target logic, so could the halting problem, which contradicts its undecidability. So yes, the formula can depend on the machine as much as it wants. See here ...


3

First, the expressive power of SQL is less clear-cut than it seems. The aggregate, grouping, and arithmetic features of SQL turn out to have quite subtle effects. A priori, it seems feasible that by some encoding of algebraic operators using these features, one could actually express reachability in SQL. It turns out this isn't actually the case for SQL-...


3

First off, I assume you also want to have a binary relation on the domain, acting as a linear order: <. Furthermore, I assume you want to deal with existential second-order logic, which in general allows more than one existential quantifiert. Then, you can employ Fagin's theorem: wikipedia And what remains to show is that you can recognize the language $...


1

After a little bit of struggling I found an easy answer by myself: We can "define" a ternary relation: $T(x,y,z) \equiv M(x,y) \land M(y,z) \land M(z,x)$ Then we can define $L$ in this way: $\exists M$ such that $\forall x,y \;.\; U_a(x) \land U_b(y) \to x < y$ ($a$s before $b$s) $\forall z \;.\; U_b(z) \to \exists x, y \;.\; U_a(x) \land U_a(y) \land ...


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

Boolean queries are a special case of general queries. You can take $\tau$ to be some convenient vocabulary and choose a pair of $\tau$-structures to represent "true" and "false". FOr a concrete example, take $\tau$ to be the vocabulary with a single nullary relation symbol $T$. Now, associate "true" with the $\tau$-structure $\mathfrak{T}$ that has $|...


1

A state is simply an assignment of all possible variables of a system to values. A state transition then means a transition from one possible set of values of variables to another set of values. To see how this might be useful, imagine a set of two switches $S$ and a light bulb $B$ that are connected to emulate some unknown logical gate. If you want to ...


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