Derive a boolean first-order query, Mathematics

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

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







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
Related Questions

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

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

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


what is an equation for circle?..

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

i have a question about discret math

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)

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