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 : Bolzano-Weierstrass property The

The Bolzano-Weierstrass property does not hold in C[0, ¶] for the infinite set A ={sinnx:n<N} : A is infinite; Show that has no “ limit points”.

Q : State Prime number theorem Prime number

Prime number theorem: A big deal is known about the distribution of prime numbers and of the prime factors of a typical number. Most of the mathematics, although, is deep: while the results are often not too hard to state, the proofs are often diffic

Q : Numerical Analysis Hi, I was wondering

Hi, I was wondering if there is anyone who can perform numerical analysis and write a code when required. Thanks

Q : **How do it? integral e^(-t)*e^(tz) t**

integral e^(-t)*e^(tz) t between 0 and infinity for Re(z)<1

Q : Maths A cricketer cn throw a ball to a

A cricketer cn throw a ball to a max horizontl distnce of 100m. If he throws d same ball vertically upwards then the max height upto which he can throw is????

Q : Formal logic It's a problem set, they

It's a problem set, they are attached. it's related to Sider's book which is "Logic to philosophy" I attached the book too. I need it on feb22 but feb23 still work

Q : Problem on Prime theory Suppose that p

Suppose that p and q are different primes and n = pq. (i) Express p + q in terms of Ø(n) and n. (ii) Express p - q in terms of p + q and n. (iii) Expl

Q : Theorem-Group is unique and has unique

Let (G; o) be a group. Then the identity of the group is unique and each element of the group has a unique inverse.In this proof, we will argue completely formally, including all the parentheses and all the occurrences of the group operation o. As we proce

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 : 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 1421541 Solved problems, classrooms assignments, textbook's solutions, for quick Downloads

No hassle, Instant Access

Start Discovering

18,76,764

1933625
Asked

3,689

Active Tutors

1421541

Questions
Answered

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

Submit Assignment