--%>
Assignment Help - homework help

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.

(c) There is a simple path (that is, a path without repeated vertices) of even length among two specified vertices.

(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.

   Related Questions in Mathematics

  • Q : Law of iterated expectations for

     Prove the law of iterated expectations for continuous random variables. 2. Prove that the bounds in Chebyshev's theorem cannot be improved upon. I.e., provide a distribution that satisfies the bounds exactly for k ≥1, show that it satisfies the bounds exactly, and draw its PDF. T

    		•
  • Q : Problem on mass balance law Using the

    Using the mass balance law approach, write down a set of word equations to model the transport of lead concentration. A) Draw a compartmental model to represent  the diffusion of lead through the lungs and the bloodstream.

    		•
  • 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 : The mean of the sampling distribution

    1. Caterer determines that 87% of people who sampled the food thought it was delicious. A random sample of 144 out of population of 5000 taken. 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 : Problem on mixed-strategy equilibrium

    Assume three Offices (A, B, & C) in downtown,  simultaneously decide whether to situate in a new Building. The payoff matrix is illustrated below. What is (are) the pure stratgy Nash equilibrium (or equilibria) and mixed-strtegy equilibrium of the game?

    		•
  • 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 : Nonlinear integer programming problem

    Explain Nonlinear integer programming problem with an example ?

    		•
  • Q : What is Non-Logical Vocabulary

    Non-Logical Vocabulary: 1. Predicates, called also relation symbols, each with its associated arity. For our needs, we may assume that the number of predicates is finite. But this is not essential. We can have an infinite list of predicates, P

    		•
  • Q : Who firstly use the finite-difference

    Who firstly use the finite-difference method?

    		•
  • Q : Define Big-O notation Big-O notation :

    Big-O notation: If f(n) and g(n) are functions of a natural number n, we write f(n) is O(g(n)) and we say f is big-O of g if there is a constant C (independent of n) such that f

    		•