### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Mathematical Basis for Computing CSE 607

Syracuse

GPA 3.74

### View Full Document

## 45

## 0

## Popular in Course

## Popular in Computer Engineering

This 31 page Class Notes was uploaded by David Mayert on Tuesday October 20, 2015. The Class Notes belongs to CSE 607 at Syracuse University taught by Howard Blair in Fall. Since its upload, it has received 45 views. For similar materials see /class/225559/cse-607-syracuse-university in Computer Engineering at Syracuse University.

## Reviews for Mathematical Basis for Computing

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/20/15

Setbased Answer Set Programming H A Blair1 J B Remmel2 V W Marek3 1Syracuse University EECS Dept biairecs syr edu ZUCSD Mathematics Dept remmei iltieene ucsd edu 3University of Kentucky CS Dept marek cs uky edu February 19 2008 Overview what and how a What I Answer set programs Stable models of datalog programs provide answers to combinatorial search and decision problems 0 What ll Setbased answer set programs Setbased stable models of setbased datalog programs provide answers to combinatorial search and decision problems in special problem domains39 0 How By spatially constrained predicate logic this is applied logic It is not at this stage of development intended to address foundational questions Terms to be defined are in dark green 0 Why Satisfying constraints in specific problem domains can be aided by knowledge specific to the domain Put another way reasoning to satisfy constraints seems to be at least partly semantic in a manner characteristic of the domain Plan of the talk 0 Some problems 9 Some results 0 Datalog programs We start in with technical details here 9 Validity stable models and answerset programming 6 The basic move 6 Setbased datalog programs 0 Setbased validity stable models and setbased answerset programming 9 Examples 9 Representing continuous structure Relation to intuitionistic propositional logic 1 Some problems o How does the already understood quotmodel theoryquot of answer set programs compare to the setbased setup 0 Interfacing logic with domainspecific knowledge how 0 What can we do with setbased answer set programs 0 Relationships to all the rest of logic 2 Some results o Setbased logic is naturally threevalued o Monotone programs need not be continuous o The interface between logic and domain specific knowledge is implemented with monotone idempotent operators a Negative knowledge and positive knowledge can be independently characterized in the same program while 0 The characterization of stable models is preserved 0 Continuous structure is representable o lntuitionistic propositional logic is a special case 31 Datalog programs o The underlying language is that of predicate logic constant symbols but no other function symbols 0 A datalog program is a finite set of program clauses partitioned into two subsets 1 the EDP extensional database and 2 the IDB intensional database The partition satisfies several constraints 0 A program clause is a formula AltL1A A L where A is an atomic formula atom and each Li called a literal is either an atomic formula or the negation of an atom A is the headof the clause and L1 A Ln is the body of the clause lf L is an atom it is called a positive literal otherwise it is a negative literal 32 Datalog programs the EDB o A formula is called ground ih has no free variable occurrences o A factis a ground atom o The EDB consists of facts 32 Datalog programs the IDB 0 Variables occurring in the heads of program clauses of the IDB are range restricted ie they must occur in a positive literal in the body of the clause Needed for efficient database query processing dropped in theory in answer set programming 0 No predicate symbol occurring in the EDB occurs in the head of an IDB clause A stratification restriction An inessential restriction often dropped 41 Validity o The Herbrand base of a language E for predicate logic is the set of all ground atoms of the language 0 An Herbrand interpretation for E is a subset of the Herbrand base o Remark An Herbrand interpretation is a structure in the usual sense its universe is the set of constants of the language and the true instances of the interpretation of a predicate symbol p are the tuples of constants a1 ak for which the corresponding ground atom pa1 ak is in I This determines the ground atoms A valid in U l A o Validity of formulas is extended to all formulas in a standard way A model of a set of formulas and a fortiori a program therefore has the usual definition 421 Stable models preliminaries o The notion of a stable model depends on a property of Horn programs ie programs without negations in their clause bodies They have a least Herbrand model Think of Horn programs as inductive definitions 0 An Herbrand model lot a program is supported ill for every ground atom A in I there is a ground instance A lt L1 A A Ln of a clause in the program forwhose body L1 A A Ln is valid in l o The least Herbrand model of a Horn program is supported 422 Stable models The GelfondLifschitz transform 0 Given a program P and Herbrand interpretation I we obtain the set groundP of all ground instances of the clauses of P and use Ito evaluate negative literals in the clause bodies 0 If I does not satisfy the negative literals of a clause body I cannot satisfy the clause body Eliminate the clause from groundP lf ldoes satisfy all of the negative literals of a clause body then satisfies the clause body iff satisfies the result of removing the negative literals from the body Remove the negative literals o The resulting program GLP is Horn GLP is the GelfondLifschitz transform of P with respect to l O 423 Stable models The Definition is a stable model of P ill is the least Herbrand model of the GelfondLifschitz transform of P with respect to l o The idea is to use Ito evaluate the negative literals in ground clause bodies to obtain a Horn program I is a stable model of P ill I is the least model of the resulting Horn program 0 That a stable model of P is in fact a model requires an easy proof o Stable models are minimal supported models Hence the collection of stable models of P forms an antichain with respect to set inclusion 424 Stable models An example are the minimal supported models Only p is stable 41 Answer set programming 0 Datalog with the stratification and range restrictions dropped 0 The IDB defines the general form of a combinatorial search problem a The EDB and an extension of the IDB defines a specific instance of the problem 0 The stable models of the resulting program give the answers to the problem 432 Answer set programming an example 0 Graph coloring Can a directed graph39s vertices be colored such that no two adjacent vertices have the same color 0 A lt colorofXC A colorofYC A color C A vertexX A vertexY A edgeXY A A 0 Assuming A is not used differently elsewhere in the program any stable model of a program containing this clause must falsify colorofXC A colorofYC A color A vertexX A vertexY A C edgeXY 433 Answer set programming an example colorred colorgreen colorblue m o co m A 37 o v colorofXred colorofXgreen colorofXbue A A A TTTTTT colorofXgreen A colorofXblue colorofXred A colorofXblue colorofXgreen A colorofXred colorofXred A colorofXgreen A A colorofXred A colorofXbue A A colorofXgreen A colorofXbue A A 5 The basic move 0 With Herbrand interpretations l l A it and only it A e I A an atom a Let the sense A of a ground atom A be the set A Then it follows that ll A iii A g l 0 Now let sense map the Herbrand base into a powerset of some set X and define Y i A iii A g Y for each member Y of the powerset of X 6 Setbased datalog programs o The difference between ordinary programs and setbased programs is that the underlying language is spatially augmented o A spatially augmented firstorder language spatial language for short E is a triple L X where 0 L is a language for predicate logic 9 X is a nonempty possibly infinite set called the interpretation space and 0 H is a mapping from the ground atoms of L to the power set of X called the sense assignment If A is a ground atom then A is called the sense of A 7 1 Validity of ground literals a Y i A iii A g Y for each member Y of the powerset of X 0 strong negation 3valued Y l5 A ih Y m A Q 0 weak negation 2valued Y lquotquot A iii A g Y 7 2 Validity of other nonnegations 0 Begin with la where a e 3 W defined on ground literals o Yla gtmpi Yla gtand Ylaw o Yla gtzpih Yla gtor Ylaw 0 Y la gt ed ih Y lazp implies Y la gt 9 Y la VX4pX ih Y la Me all constants e 0 Y la 3X4pX ih Y la Me some constant e 721 Monotone idempotent operators 7 o monotone Y1 g Y2 implies opY1 g opYz o idempotent opopY opY 722 1step consequence operator of a program P 0 Given a miop opJr 2X a 2X and Horn program P 0 ILop A if and only if opA g I Then G TPop 010W where AHLH 7 Ln 6 P7 H0p Li1n We then say that a supported model relative to opJr of P is a fixed point of Tao9 723 Iterating Tpop TPop T0 I I TPop Ta I TPopTPop Ta Tao9 TA I 0p U TP0p Ta 07 limit ozlt 724 Setbased Horn Programs Theorem Given a miop opl the least model of a Horn setbased logic program P exists and is closed under opJr is supported relative opl and is given by Tao9 T 0 for the least ordinal a at which a fixed point is obtained 725 Setbased Horn Programs not continuous Let E L X H where L has four unary predicate symbols p q r and s and countably many constants e0 e1 X is the set NUN where N is the set of natural numbers 0 1 2 H is specified by qe 0 n lPenll 077n1 lrenll N llsenll N The EDB is empty and the IDB is qeo e pX e qX and seo lt reo Now after to iterations upward from the empty interpretation reo becomes satisfied One more iteration is required to reach an interpretation that satisfies se0 where the least fixed point is attained 726 Validity with respect to a pair of miops Suppose that 73 set based logic program over X and opJr and op are miops on X Let a e 3 W I Given any atom A and set J g X then we say J kiloatop A if and only if opA Q J ll Given any atom A and set J g X then we say J Emaatop AA If and only If op A m J op ll Given any atom A and set J g X then we say J l AA if and only if op A g J W IIii p op 727 Stable models semantics The two types of satisfaction relations for negative literals immediately yield two types of 0 supported models based on two types of onestep consequence operators T 0W op and TF39 quot ophop 0 two types of Geh ondLifschitz transform GLf GLllllppaor o and two types of stable model semantics d llll p op 3 8 A short example oXR2 0 Two atoms a b 0 d where a b 0 and d are reals o a b and 0 d denotes the line segments connecting a to b and 0 to d respectively 0 Let the sense of these atoms be the corresponding subsets ie let a b a b and 0 d 0 d 0 Let opJr op opconvex the convex closure operator 82 A short example 0 Consider the following program 73 1 a b e acd 2 070 s ayb 0 There are four possible candidates for stable models in this case namely i 0 ii a b iii 0 d and iv OPCOHV8Xa7 b7 C7 o If we are considering sstable models where C if and only if op C m J op 0 J l5 o ope then if afb and 0 d are disjoint then ii and iii are sstable models 8 A short example If we are considering Wstable models where J V39f pptoJ C if and only if op C g J then there are no Wstable models if a b 0 d ii is a Wstable model if 0 d g a b iii is Wstable model if a b g 0 d and ii and iii are Wstable models if neither a b g 0 d nor 0 d g a b

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "I made $350 in just two days after posting my first study guide."

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.