Problem on Datalog for defining properties

The focus is on the use of Datalog for defining properties and queries on graphs.

(a) Assume that P is some property of graphs definable in the Datalog. Show that P is preserved beneath extensions and homomorphisms. That is, when G is a graph satisfying P, then for every supergraph of G (i.e., graph extending G) satisfies P, and when h is a graph homomorphism, then h(G) satisfies P. Which of the below properties and queries on graphs are definable in the Datalog?

(b) The number of vertices are even.

(d) The binary relation? Having all pairs of vertices (a, b) for which there is a path of even length from a to b.

Given either a Datalog program stating the property or query or an argument why the property or query is not definable in the Datalog.

View Complete Question

Related Questions in Mathematics

Q : State Fermat algorithm The basic Fermat

The basic Fermat algorithm is as follows: Assume that n is an odd positive integer. Set c = [√n] (`ceiling of √n '). Then we consider in turn the numbers c2 - n; (c+1)2 - n; (c+2)2 - n..... until a perfect square is found. If th

Q : Row-echelon matrix Determine into which

Determine into which of the following 3 kinds (A), (B) and (C) the matrices (a) to (e) beneath can be categorized: Type (A): The matrix is in both reduced row-echelon form and row-echelon form. Type (B): The matrix

Q : Econ For every value of real GDP,

For every value of real GDP, actual investment equals

Q : What is Big-O hierarchy The big-O

The big-O hierarchy: A few basic facts about the big-O behaviour of some familiar functions are very important. Let p(n) be a polynomial in n (of any degree). Then logbn is O(p(n)) and p(n) is O(an<

Q : Ordinary Differential Equation or ODE

What is an Ordinary Differential Equation (ODE)?

Q : Logic and math The homework is attached

The homework is attached in the first two files, it's is related to Sider's book, which is "Logic for philosophy" I attached this book too, it's the third file.

Q : Statistics Caterer determines that 37%

Caterer determines that 37% of people who sampled the food thought it was delicious. A random sample of 144 out of population of 5000. The 144 are asked to sample the food. If P-hat is the proportion saying that the food is delicious, what is the mean of the sampling distribution p-hat?

Q : First-order formulas over the

Consider the unary relational symbols P and L, and the binary relational symbol On, where P(a) and I(a) encode that a is apoint and a (sraight) line in the 2-dimensional space, respectively, while On(a,b) encodes that a is a point, b is a line, and o lies on b.

Q : Probability assignments 1. Smith keeps

1. Smith keeps track of poor work. Often on afternoon it is 5%. If he checks 300 of 7500 instruments what is probability he will find less than 20substandard? 2. Realtors estimate that 23% of homes purchased in 2004 were considered investment properties. If a sample of 800 homes sold in 2

Q : Problem on Fermats method A public key

A public key for RSA is published as n = 17947 and a = 3. (i) Use Fermat’s method to factor n. (ii) Check that this defines a valid system and find the private key X.

Discover Q & A

Leading Solution Library

Avail More Than 1424369 Solved problems, classrooms assignments, textbook's solutions, for quick Downloads

No hassle, Instant Access

Start Discovering

18,76,764

1930039
Asked

3,689

Active Tutors

1424369

Questions
Answered

Start Excelling in your courses, Ask an Expert and get answers for your homework and assignments!!

Submit Assignment