Notices
Results 1 to 3 of 3

Thread: Can anyone help me make a directed graph for this algorithm?

  1. #1 Can anyone help me make a directed graph for this algorithm? 
    New Member
    Join Date
    Nov 2011
    Posts
    2
    Show how to implement the stingy algorithm for Horn formula satisfiability in time that is linear in length of the formula (the no. of occurrences of literals in it.)
    Use a directed graph, with one node per variable to represent the implications.)
    (This is exercise 5.32 in the book Algorithms byS. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani)Below is an efficient algorithm I got from Logic for Computer Scientists/Propositional Logic/Horn clauses - Wikibooks, open books for an open world that is O(l).
    Deciding Satisfiability of Horn Formulae
    1. If there is a subformula of the kind label every occurrence of A in F.
    2. Apply the following rules until none of them is applicable:
      • If is a subformula and are all labeled and B is not labeled then label every occurrence of B in F.
      • If is a subformula and are all labeled then Stop: Unsatisfiable
    3. Stop: Satisfiable The assignment iff A is labeled is a model.


    Reply With Quote  
     

  2.  
     

  3. #2  
    Suspended
    Join Date
    Apr 2007
    Location
    Pennsylvania
    Posts
    8,795
    It looks like homework. Is it?


    Reply With Quote  
     

  4. #3  
    New Member
    Join Date
    Nov 2011
    Posts
    2
    yup.. its a very hard homework.. we were never taught on how to make directed graphs...
    Reply With Quote  
     

Similar Threads

  1. Graph theory help!
    By m84uily in forum Mathematics
    Replies: 2
    Last Post: May 15th, 2011, 09:08 PM
  2. what's the name of the graph
    By FuturePasTimeCE in forum Mathematics
    Replies: 6
    Last Post: December 20th, 2010, 07:04 PM
  3. Graph coloring algorithm
    By MagiMaster in forum Mathematics
    Replies: 7
    Last Post: April 17th, 2008, 04:42 PM
  4. Directed Magnetism
    By Kabooom in forum Physics
    Replies: 6
    Last Post: January 21st, 2007, 04:47 AM
Bookmarks
Bookmarks
Posting Permissions
  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •