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

Decimal representations of some basic angles, Decimal representations of so... Decimal representations of some basic angles: As a last quick topic let's note that it will, on occasion, be useful to remember the decimal representations of some basic angles. S

Fuzzy decisionmaking using minimization of regret, why we use decision maki... why we use decision making using minimization of regret method in uncertainty?

Apply depth-first-search to find out the spanning tree, Apply depth-first-s... Apply depth-first-search to find out the spanning tree for the subsequent graph with vertex d as the starting vertex.        Ans: Let us begin with node'd'. Mark d as vi

Problem solving, Sales price of a compact disc player is $200, each new cd ... Sales price of a compact disc player is $200, each new cd is on sale for $12. kyle purchases a player and some cds for $224. how many cds were purchased?

What is 2^5, What is 2 5 ? 2 5 = 2 ×2 ×2 ×2 ×2 = 32 What is 2 5 ? 2 5 = 2 ×2 ×2 ×2 ×2 = 32

Determine the length of the field, A rectangular field is to be fenced in c... A rectangular field is to be fenced in completely. The width is given as 22 yd and the total area is 990 yd 2 . Determine the length of the field? a. 31 yd b. 45 yd c. 968

Free - undamped vibrations, It is the simplest case which we can consider. ... It is the simplest case which we can consider. Unforced or free vibrations sense that F(t) = 0 and undamped vibrations implies that g = 0. Under this case the differential equation

The cost of renting a bike at the local bike is y = 2x + 2, The cost of re... The cost of renting a bike at the local bike shop can be represented through the equation y = 2x + 2, where y is the total cost and x is the number of hours the bike is rented. Whi

Intercepts, The last topic that we want to discuss in this section is that ... The last topic that we want to discuss in this section is that of intercepts.  Notice that the graph in the above instance crosses the x-axis in two places & the y-axis in one plac

Geometry, how much is this how much is this