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
Write an algebraic expression for “Julie runs three miles less than twice the number of miles,

A manufacturer assures his customers that the probability of having defective item is as 0.005. A sample of 1000 items was inspected. Determine the probabilities of having the give

How do you find the area of a circle given the diameter?

Tangents with Parametric Equations In this part we want to find out the tangent lines to the parametric equations given by X= f (t) Y = g (t) To do this let's first r

Tori was asked to provide an example of the commutative property of addition. Which of the subsequent choices would be correct? Using the simple interest formula Interest = pr

A rectangles lenth is (x+4) and width is (x+3).By adding binomials give its perimiter

Define Markov process. Markov process is one in which the future value is independent of the past values, given the current value