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).

Posted Date: 3/1/2013 12:29:43 AM | Location : United States

Ask an Expert

Related Discussions:- Derive a boolean first-order query, Assignment Help, Ask Question on Derive a boolean first-order query, Get Answer, Expert's Help, Derive a boolean first-order query Discussions

Write discussion on Derive a boolean first-order query
Your posts are moderated

Write your message here..

Related Questions

Algorithm, sinx sinx

Using calculus method, Sheldon as the day for the challenge gets closer wan... Sheldon as the day for the challenge gets closer wants to enter the race. Not being content with an equal start, he wants to handicap himself by giving the other yachts a head star

Student, Patio measures 24 meters square. Patio stone are 30 cm each side. ... Patio measures 24 meters square. Patio stone are 30 cm each side. How many stones are required to cover the patio?

Math, Verify Louisville''s formula for y "-y" - y'' + y = 0 in (0, 1) quest... Verify Louisville''s formula for y "-y" - y'' + y = 0 in (0, 1) question..

Complete 75 tree fraction, solve question solve question

Sum, what is an equation for circle?.. what is an equation for circle?..

Divergence test - sequences and series, Divergence Test Once again... Divergence Test Once again, do NOT misuse this test.  This test only says that a series is definite to diverge if the series terms do not go to zero in the limit.  If the

Discret math, i have a question about discret math i have a question about discret math

Sqares, Recently I had an insight regarding the difference between squares ... Recently I had an insight regarding the difference between squares of sequential whole numbers and the sum of those two whole numbers. I quickly realized the following: x + (x+1)

Decision trees illustration, A company is considering whether to enter a ve... A company is considering whether to enter a very competitive market. In case company decided to enter in market this must either install a new forging process or pay overtime wages