|
Technical Reports |
2001 | 2002 | 2003 | 2005 | 2007 | 2008 |
| NMSU-CS-2001-001 |
| Set Unification |
| A. Dovier, E. Pontelli, and G. Rossi |
| Abstract: The goal of this paper is to provide a uniform overview of the unification problem in algebras capable of describing sets. The problem has been tackled, directly and indirectly, by many researchers and it can find important applications in various research areas - e.g., deductive databases, theorem proving, static analysis, rapid software prototyping. The problem has been explored in depth, but the various solutions proposed are spread across a large literature, and some of the approaches have been ignored and/or rediscovered by different researchers. In this paper we provide a uniform presentation of unification of sets, starting with the simpler instances of the problem - e.g., matching of completely ground terms - and proceeding to progressively more complex problems - e.g., unification between general ACI terms. The algorithms presented are partly drawn from the literature - and properly revisited and analyzed - and partly novel proposals. In particular we present a new goal-driven algorithm for general ACI unification and a new algorithm (with a simple termination proof) for general (Ab)(Cl) unification. However, the major contribution of this work is to provide the first uniform presentation of the problem, covering all its different instances, and surveying the different solutions developed. |
| Download document: ps pdf |
| NMSU-CS-2001-002 |
| An Argument-Based Approach to Reasoning with Specificity |
| P.M.Dung and T.C.Son |
| Abstract: We present a new priority-based approach to reasoning with specificity which subsumes inheritance reasoning. The new approach differs from other priority-based approaches in the literature in the way priority between defaults is handled. Here, it is conditional rather than unconditional as in other approaches. We show that any unconditional handling of priorities between defaults as advocated in the literature until now is not sufficient to capture general defeasible inheritance reasoning. We propose a simple and novel argumentation semantics for reasoning with specificity taking the conditionality of the priorities between defaults into account. Since the proposed argumentation semantics is a form of stable semantics of nonmonotonic reasoning, it inherits a common problem of the latter where it is not always defined for every default theory. We propose a class of stratified default theories for which the argumentation semantics is always defined. We also show that acyclic and consistent inheritance networks are stratified. We prove that the argumentation semantics satisfies the basic properties of a nonmonotonic consequence relation such as deduction, reduction, conditioning, and cumulativity for well-defined and stratified default theories. To use well-known algorithms of Reiter's default logic as algorithms for computing the newly defined nonmonotonic consequence relation, we transform default theories with specificity into semantically equivalent Reiter's default theories. We show that computing the entailment relation of default theories is at least {\bf NP}-hard. To attack this problem, we present an approximation of this relation, called the grounded entailment relation, that can be computed in polynomial time for a class of default theories, called default networks, which covers the class of acyclic inheritance networks. |
| Download document: ps pdf |
| NMSU-CS-2001-003 |
| Proceedings of the Colloquium on Implementation of Constraint and Logic Programming Systems (CICLOPS 2001) |
| E. Pontelli (Ed.) |
| Abstract: This volume contains the proceedings of the First Colloquium on Implementation of Constraint and Logic Programming Systems (CICLOPS). The workshop took place in Cyprus on December 1st, 2001, as a satellite event to the International Conference on Logic Programming and the Constraint Programming Conference. This workshop is a continuation of the series of workshops on Implementations of Logic Programming Systems, previously held with considerable success in Budapest (1993), Santa Margherita (1994) and Ithaca (1994), as well as the Compulog Net workshops on Parallelism and Implementation Technologies held in Madrid (1993-4), Utrecht (1995), Bonn (1996), Port Jefferson (1997), Manchester (1998), Las Cruces (1999), and London (2000). This year, the event will join forces with TRICS (Techniques for Implementing Constraint Programming Systems), previously held in Singapore (2000), thus providing coverage to implementation technology for both Logic and Constraint Programming. The last years have seen continuous progress in the computing technology available both for the academic and commercial computing environments. Examples include improved processor performance, increased memory capacity and bandwidth, faster networking technology, and Operating System support for cluster computing. Combined with recent advances in compilation technologies, these improvements are causing high-level languages to be regarded as good candidates for programming complex, real world applications. Logic Programming and Constraint Programming, in particular, seem to offer one of the best alternatives, as they couple a very high level of abstraction and a declarative nature with an extreme flexibility in the design of its execution model. The main intent of this workshop is to bring together, in an informal and friendly setting, key researchers on implementation technologies for logic and constraint-based languages and systems, in order to promote a much needed exchange of ideas and feedback on recent developments. |
| Download document: ps pdf |