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

Finding the area of a triangle, Q. Finding the Area of a Triangle? Ther... Q. Finding the Area of a Triangle? There are three commonly used methods to find the area of a triangle. The method you use to find the area depends on the information you kno

World problem, Buses to Acton leave a bus station every 24 minutes. Buses t... Buses to Acton leave a bus station every 24 minutes. Buses to Barton leave the same bus station every 20 minutes. A bus to Acton and a bus to Barton both leave the bus station at 9

Finite population correction factor or fpcf), Finite Population Correction ... Finite Population Correction Factor Or Fpcf) If a specified population is relatively of small size and sample size is more than 5 percent of the population then the standard er

Transforming the base of logarithms, Suppose that we know the logarit... Suppose that we know the logarithms of all numbers which are expressed to base 'a' and we are required to find the logarithms of all these numbers to base 'b'. We

Example of a function - inflection point, 1. (a) Give an example of a funct... 1. (a) Give an example of a function, f(x), that has an inflection point at (1, 4). (b) Give an example of a function, g(x), that has a local maximum at ( -3, 3) and a local min

Example of inflection point-differential equation, Example of inflection po... Example of inflection point Determine the points of inflection on the curve of the function y = x 3 Solution The only possible inflexion points will happen where

Micrometer, how to use a micrometer how to use a micrometer

Area problem, Area Problem Now It is time to start second kind of inte... Area Problem Now It is time to start second kind of integral: Definite Integrals.  The area problem is to definite integrals what tangent & rate of change problems are to d

Comparison test or limit comparison test, Comparison Test or Limit Comparis... Comparison Test or Limit Comparison Test In the preceding section we saw how to relate a series to an improper integral to find out the convergence of a series.  When the inte

Matric, fgdg ggghfr hhrhfrf hfrrg jhj hjgg dear friend ghr tu vgu jyyiu ui ... fgdg ggghfr hhrhfrf hfrrg jhj hjgg dear friend ghr tu vgu jyyiu ui u huik bgyuiiyts husk