Derive a boolean first-order query, Mathematics

Assignment Help:

Consider a database whose universe is a finite set of vertices V and whose unique relation .E is binary and encodes the edges of an undirected (resp., directed) graph G: (V, E). Each undirected edge between the nodes o and u (resp., directed edge from the node v to the node u) is encoded by the two atoms E (v, u) and E (u, v) (resp., by the single atom E (v, u)).

Consider the pairs of stucture (undirected (resp., directed) graphs) shown in Fig. 1. Suppose that the graphs are encoded in a database as explained above. For each pair, answer the following questions:

1. What is the smallest quantifier rank k for which the spoiler wins the k-move Ehrenfeucht-Fraisse game on the pair of structure?

2. Derive a Boolean first-order query from your winning strategy that is true on one structure but not on the other (you can use the equality relation between vertices).

2382_Derive a Boolean First-Order Query.png


Related Discussions:- Derive a boolean first-order query

Lesson 6 Homework Practice, For every girl taking classes at the martial ar...

For every girl taking classes at the martial arts school there are 3 boys who are taking classes at the school. If there are 236 students taking classes write and solve a proportio

Find out the radius of convergence, Example: Find out the radius of conver...

Example: Find out the radius of convergence for the following power series. Solution : Therefore, in this case we have, a n = ((-3) n )/(n7 n+1 )   a n+1 = (

Proof of constant times a function, Proof of Constant Times a Function: ...

Proof of Constant Times a Function: (cf(x))′ = cf ′(x) It is very easy property to prove using the definition given you a recall, we can factor a constant out of a limit. No

Probability, Question: There are 6 letters and 6 self addressed envelopes.W...

Question: There are 6 letters and 6 self addressed envelopes.What is the probability that atleast 1 is placed correctly?? Ans: If we let A be the event that letter A is in the cor

Triangles, about scalene,equilateral and isosceles.

about scalene,equilateral and isosceles.

Evaluating a function, Evaluating a Function You evaluate a function by...

Evaluating a Function You evaluate a function by "plugging in a number". For example, to evaluate the function f(x) = 3x 2 + x -5 at x = 10, you plug in a 10 everywhere you

probability , An engineer has 200 resistors that he keeps in one box. Resi...

An engineer has 200 resistors that he keeps in one box. Resistors are colored to help their identification, and in this box there are 30 white resistors, 50 black resistors, 80 red

Find least number of cables required to connect 100 computer, Find out the ...

Find out the least number of cables required to connect 100 computers to 20 printers to assurance that 20 computers can directly access 20 different printers.  Justify your answer.

Find the sum of all 3 digit numbers which leave remainder 3, Find the sum o...

Find the sum of all 3 digit numbers which leave remainder 3 when divided by 5. Ans:    103, 108..........998   a + (n-1)d = 998

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd