Derive a boolean first-order query, Mathematics

Assignment Help:

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


Related Discussions:- Derive a boolean first-order query

Circles and cones, length of subnormal to the curve y2=2x+1 at (4,3)

length of subnormal to the curve y2=2x+1 at (4,3)

Vector arithmetic - addition, Vector Arithmetic In this part we need t...

Vector Arithmetic In this part we need to have a brief discussion of vector arithmetic. Addition We will begin with addition of two vectors. Thus, given the vectors a

How many miles to the gallon does marci''s car get, Marci filled her car's ...

Marci filled her car's gas tank on Monday, and the odometer read 32,461.3 miles. On Friday while the car's odometer read 32,659.7 miles and she filled the car's tank again. It will

Find the value of a+b, If A, B are acute angles and sinA= cosB, then find t...

If A, B are acute angles and sinA= cosB, then find the value of A+B. Ans:    A + B = 90 o

Calculus, I need an explanation of "the integral, from b to a, of the deriv...

I need an explanation of "the integral, from b to a, of the derivative of f (x). and, the integral from a to b. of the derivative of f(t) dt.

How many more cm are required to reach the average monthly, Thomas is remai...

Thomas is remaining track of the rainfall in the month of May for his science project. The first day, 2.6 cm of rain fell. On the second day, 3.4 cm fell. On the third day, 2.1 cm

Cone - three dimensional spaces, Cone - Three dimensional spaces The be...

Cone - Three dimensional spaces The below equation is the general equation of a cone. X 2 / a 2 + y 2 /b 2 = z 2 /c 2 Here is a diagram of a typical cone. Not

What are the average total repair costs per month, An automobile manufactur...

An automobile manufacturer needs to build a data warehouse to store and analyze data about repairs of vehicles. Among other information, the date of repair, properties of the vehic

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd