Technical Reports

Technical Reports

2001 | 2002 | 2003 | 2005 | 2007 | 2008 |

NMSU-CS-2005-001

Defining well-founded semantics for revision programming

Inna V. Pivkina

Abstract: Revision programming is a formalism to describe and enforce constraints on belief sets, databases, and more generally, on arbitrary sets. In this paper we describe four approaches to defining well-founded semantics of revision programming and approximating justified revisions. The first two approaches are obtained via embeddings of revision programs into logic programs. The other two approaches are specific to revision programming and provide approximations for justified revisions.

Download document: ps pdf

NMSU-CS-2005-002

Introducing a Primary Historical Source Project in a Discrete Mathematics and Computer Science Course: Counting Triangulations of a Polygon

Karen Villaverde, Desh Ranjan, and David Pengelley

Abstract: This paper presents a non traditional methodology of instruction which introduces a primary historical source project in an undergraduate course in discrete mathematics and computer science. The project provides an alternative to traditional methods of instruction that although thorough and mathematically precise, present the course material as a fast-paced news reel of facts and formulae, often memorized by the students, with the text itself offering only passing mention of the motivating problems and original work which eventually found resolution in modern mathematical concepts. The project presented in this paper allows the students to hone their verbal and deductive skills through reading, answering key questions, and studying the original work of some famous mathematicians. The students are basically given the opportunity to react to the original source in much the same way as the contemporaries of the historical masterpiece, explore the development of key and ground-breaking ideas, and rediscover the conceptual roots common to discrete mathematics and computer science. The particular course described in this paper is a Data Structures and Algorithms course and the particular historical source is an excerpt from a letter of Monsieur Lame to Monsieur Liouville on the question: Given a convex polygon, in how many ways can one partition it into triangles by means of diagonals?

Download document: pdf

NMSU-CS-2005-003

Justification and Debugging of Answer Set Programs in ASP-PROLOG

Omar Elkhatib, Enrico Pontelli, Tran Cao Son

Abstract: The paper extends the concept of justification to the context of Answer Set Programming - a recent paradigm that builds on the foundations of logic programming, answer set semantics, and non-monotonic reasoning. A justification describes the support for the truth value of each atom in an answer set of a logic program, and it can be employed as a tool for reasoning and debugging of answer set programs. The paper describes the implementation of the notion of justification in the ASP-PROLOG system along with some examples of its applications.

Download document:

NMSU-CS-2005-004

Justification and Debugging of Answer Set Programs in ASP-Prolog

Omar Elkhatib, Enrico Pontelli, Tran Cao Son

Abstract: The paper extends the concept of justification to the context of answer set programming; a justification describes the support for the truth value of each atom in an answer set of a logic program. The notion of justification is formalized with respect to the answer set semantics of logic programs and employed as a tool for reasoning and debugging of Answer Set Programs (i.e., logic programs under answer set semantics). The paper describes the implementation of the notion of justification in the ASP-Prolog system along with some examples of its applications.

Download document: ps pdf

NMSU-CS-2005-005

Regression-based Conditional Planning in the Presence of Sensing Actions and Uncertainty in the Initial State

Le-chi Tuan, Chitta Baral, Xin Zhang, and Tran Cao Son

Abstract: Searching for conditional plans in the presence of incomplete information and sensing actions is a challenging problem for state space planners because the number of belief-states becomes doubly exponential. In this paper we present a regression planner, called CPR, to tackle such problem. The planner is built around a recently developed state-based regression formulation which is based on an approximation of sensing actions with lower complexity for conditional planning. We detail the use of heuristic and mutex computations in the development of the planner and compare it with several related contingent planners. The empirical results show that our planner is very competitive in comparison with the other related contingent planners and that our planner is less sensitive to the uncertainty and irrelevant variables in the initial state than the related progression planners.

Download document: ps pdf

NMSU-CS-2005-006

On Logic Programming with Aggregates

Tran Cao Son, Enrico Pontelli, and Islam Elkabani

Abstract: The paper presents a translational semantics for normal logic programs with aggregates. The semantics does not impose any syntactical restrictions on aggregates. It naturally extends the traditional answer set semantics. We show that it subsumes many of the previous proposals in this area, yet overcomes several drawbacks of those proposals, e.g., it does not produce non-minimal answer sets. We also discuss how the proposed approach can be extended to logic program with aggregates in the head, a class of programs that has rarely been considered. A distinguishing feature is that the approach can be easily implemented using available answer set solvers. We discuss how this can be done and describe a system that is capable of computing answer sets of programs with recursive aggregates.

Download document: ps pdf

NMSU-CS-2005-007

Hybrid Probabilistic Logic Programs with Non-monotonic Negation

Emad Saad and Enrico Pontelli

Abstract: In [20], a new Hybrid Probabilistic Logic Programs framework is proposed, and a new semantics is developed to enable encoding and reasoning about real-world applications. In this paper, we extend the language of Hybrid Probabilistic Logic Programs framework in [20] to allow non-monotonic negation, and define two alternative semantics: stable probabilistic model semantics and probabilistic well-founded semantics. Stable probabilistic model semantics and probabilistic well-founded semantics generalize stable model semantics and well-founded semantics of traditional normal logic programs, and they reduce to the semantics of original Hybrid Probabilistic Logic programs framework of [20]. It is the first time that two di erent semantics for Hybrid Probabilistic Programs with non-monotonic negation as well as their relationship are described. This development provides a foundational ground for developing computational methods for computing the proposed semantics. Furthermore, it makes it clearer how to characterize non-monotonic negation in probabilistic logic programming frameworks for commonsense reasoning.

Download document: pdf

NMSU-CS-2005-008

Improvement and Evaluation of an Efficient Methodology to Transform a Classroom Based Course into a Web Based Course

Karen Villaverde and Bharath Kanagiri

Abstract: This paper describes the improvement, evaluation, and follow ups of a methodology used to transform a classroom based course into an effective web based course which was first presented at the Science, Engineering, & Technology Education Conference on 2003. The course discussed is CS167/467 “C Programming Web Based?offered by the Computer Science department at New Mexico State University with great success since 2002, but the methodology used for the transformation can be easily applied to other courses as well. Even though it does take time to transform a classroom based course into an effective web based course, the benefits for both the instructor and especially the students out weight the initial set up time. In this paper, we describe the steps that were taken to transform the classroom based course into a web based course along with great improvements, evaluations, results, and follow ups. Furthermore, the student performance and course evaluations of the improved web based course are compared against those of the initial web based course, and the classroom based course.