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

Errors are useful in learning maths, Errors Are Useful :  While teaching c...

Errors Are Useful :  While teaching children, you must have found theft making mistakes off and on. How do you respond to the errors'? What do they tell you about the child-failur

Long distance calls cost x cent how much 5-minute call cost, A long distanc...

A long distance calls costs x cents for the first minute and y cents for every additional minute. How much would a 5-minute call cost? The cost of the call is x cents plus y ti

What is transitive relations:, R is called as a transitive relation if (a, ...

R is called as a transitive relation if (a, b) € R, (b, c) € R → (a, c) € R In other terms if a belongs to b, b belongs to c, then a belongs to c.         Transitivity be uns

Triangles, ABC is a triangle right angled at c. let BC=a, CA=b, AB=c and lr...

ABC is a triangle right angled at c. let BC=a, CA=b, AB=c and lrt p be the length of the perpendicular from C on AB. prove that cp=ab and 1/p2=1/a2+1/b2

Design an automaton that accepts only even numbers, Design an automaton tha...

Design an automaton that accepts just only even numbers of 0s and even number of 1's. Ans: The needed automata that accepts even number of 0's and even number of 1's is specifi

Twelve coworkers go out how many slices will each person get, Twelve cowork...

Twelve coworkers go out for lunch together and sequence three pizzas. Each pizza is cut within eight slices. If each person gets the similar number of slices, how many slices will

Find the sum of given equation upto n limit, Find the sum of (1 - 1/n ) + (...

Find the sum of (1 - 1/n ) + (1 - 2/n ) + (1 - 3/n ) ....... upto n terms. Ans: (1 - 1/n ) + (1 - 2/n ) - upto n terms   ⇒[1+1+.......+n terms] - [ 1/n + 2/n +....+

Greatest common factor, Greatest Common Factor The primary method for f...

Greatest Common Factor The primary method for factoring polynomials will be factoring the greatest common factor. While factoring in general it will also be the first thing

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