Lparse 1.0 User's Manual - Theoretical background

I'll write something later

Lparse 1.0 User's Manual - ASP and Smodels

Answer Set Programming (ASP) is a programming paradigm in which the programmer describes the problem using a formal language and an underlying engine finds a solution to the problem.

Smodels is a system for ASP. Smodels programs are written using standard logic programming notation. The programs are composed of atoms and inference rules. Programs represent problems, an answer to a problem is a set of atoms, called stable model, that tell which atoms are true. A Smodel program may have none, one or many stable models. The stable models may be seen as a set of rational beliefs about the program. Smodels program example:

ide_drive       :- hard_drive, not scsi_drive.
scsi_drive      :- hard_drive, not ide_drive.
scsi_controller :- scsi_drive.
hard_drive 

This program has two stable models:

M1 = { hard_drive, ide_drive }

And

M2 = { hard_drive, scsi_drive, scsi_controller }

Smodels is implemented by Patrick Simons. The above information comes from this website: Computing the Stable model semantics and their user manual

Lparse 1.0 User's Manual - Smodels simple example

Today I ran my first ASP program and find the solution using the smodels solver. I code the Node Coloring problem. In this problem we are given a number of nodes and a set of edges that connect the nodes. The problem is to use some fixed number of colors to color each node so that two adjacent nodes do not have the same color.

color1.lp:

color(red). color(blue). color(yellow).
col(X,red)    :- node(X), not col(X,blue), not col(X,yellow).
col(X,blue)   :- node(X), not col(X,red), not col(X,yellow).
col(X,yellow) :- node(X), not col(X,blue), not col(X,red).
fail          :- edge(X,Y), color(AB), col(X,AB), col(Y,AB).
compute 1 { not fail }.

graph1:

node(a). node(b).
node(c). node(d).
edge(a,b). edge(b,c).
edge(c,d). edge(d,a).

Representing a graph with four nodes and four edges.
And to run it:

$ lparse color1.lp graph1 | smodels

After that it will show the stable model for this program:

Answer: 1
Stable Model: edge(d,a) edge(c,d) edge(b,c) edge(a,b) 
node(d) node(c) node(b) node(a) 
col(a,yellow) col(c,blue) col(d,red) col(b,red) 
color(yellow) color(blue) color(red) 
True
Duration: 0.000
Number of choice points: 3
Number of wrong choices: 0
Number of atoms: 25
Number of rules: 35
Number of picked atoms: 41
Number of forced atoms: 0
Number of truth assignments: 139
Size of searchspace (removed): 12 (0)

Master in IT with Honours plan

On the 8th of February I did a presentation titled "An introduction to MapReduce". Everything went well, but I have to be more prepared for the next time. After the presentation I talked to Dr. Kewen Wang on what to do next. He said that I should implement ASP solvers with MapReduce, more exactly with Hadoop (MapReduce open source implementation).

At the moment I'm still learning ASP as I don't understand it very well. So for the next weeks I should spent some time reading about ASP (probably the seminal papers). At the same time I should practice programming ASP, learning how to do it. The latter will definitely will help me to implement ASP with Hadoop.

Following the plan. I will try to make some practical examples of ASP on my Ubuntu machine. I don't know how to compile and even code this kind of programs. I have followed this tutorial that has helped me to install the required software Knowledge Base System Group.