--%>
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 : Theorem-G satis es the right and left

    Let G be a group. (i) G satis es the right and left cancellation laws; that is, if a; b; x ≡ G, then ax = bx and xa = xb each imply that a = b. (ii) If g ≡ G, then (g-1)

    		•
  • 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 : 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 : Breakfast program if the average is

    if the average is 0.27 and we have $500 how much break fastest will we serve by 2 weeks

    		•
  • Q : Properties for polynomial Specify the

    Specify the important properties for the polynomial.

    		•
  • 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 : Explain Black–Scholes model Explain

    Explain Black–Scholes model.

    		•
  • Q : Explain trading of call options Explain

    Explain trading of call options.

    		•
  • 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 : Research Areas in Medical Mathematical

    Some Research Areas in Medical Mathematical Modelling:1. Modeling and numerical simulations of the nanometric aerosols in the lower portion of the bronchial tree. 2. Multiscale mathematical modeling of

    		•