Semantic forgetting in answer set programming

The notion of forgetting, also known as variable elimination, has been investigated extensively in the context of classical logic, but less so in (nonmonotonic) logic programming and nonmonotonic reasoning. The few approaches that exist are based on syntactic modifications of a program at hand. In this paper, we establish a declarative theory of forgetting for disjunctive logic programs under answer set semantics that is fully based on semantic grounds. The suitability of this theory is justified by a number of desirable properties. In particular, one of our results shows that our notion of forgetting can be entirely captured by classical forgetting. We present several algorithms for computing a representation of the result of forgetting, and provide a characterization of the computational complexity of reasoning from a logic program under forgetting. As applications of our approach, we present a fairly general framework for resolving conflicts in inconsistent knowledge bases that are represented by disjunctive logic programs, and we show how the semantics of inheritance logic programs and update logic programs from the literature can be characterized through forgetting. The basic idea of the conflict resolution framework is to weaken the preferences of each agent by forgetting certain knowledge that causes inconsistency. In particular, we show how to use the notion of forgetting to provide an elegant solution for preference elicitation in disjunctive logic programming.     

Role mining using answer set programming

With the increasing adoption of role-based access control (RBAC) in business security, role mining technology has been widely applied to aid the process of migrating a non-RBAC system to an RBAC system. However, because it is hard to deal with a variety of constraint conflicts at the same time, none of existing role mining algorithms can simultaneously satisfy various constraints that usually describe organizations’ security and business requirements. To extend the ability of role mining technology, this paper proposes a novel role mining approach using answer set programming (ASP) that complies with constraints and meets various optimization objectives, named constrained role miner (CRM). Essentially, the idea is that ASP is an approach to declarative problem solving. Thus, either to discover RBAC configurations or to deal with conflicts between constraints, ASP programs do not need to specify how answers are computed. Finally, we demonstrate the effectiveness and efficiency of our approach through experimental results.     

An introduction to fuzzy answer set programming

In this paper we show how the concepts of answer set programming and fuzzy logic can be successfully combined into the single framework of fuzzy answer set programming (FASP). The framework offers the best of both worlds: from the answer set semantics, it inherits the truly declarative non-monotonic reasoning capabilities while, on the other hand, the notions from fuzzy logic in the framework allow it to step away from the sharp principles used in classical logic, e.g., that something is either completely true or completely false. As fuzzy logic gives the user great flexibility regarding the choice for the interpretation of the notions of negation, conjunction, disjunction and implication, the FASP framework is highly configurable and can, e.g., be tailored to any specific area of application. Finally, the presented framework turns out to be a proper extension of classical answer set programming, as we show, in contrast to other proposals in the literature, that there are only minor restrictions one has to demand on the fuzzy operations used, in order to be able to retrieve the classical semantics using FASP.     

Possibilistic uncertainty handling for answer set programming

In this work, we introduce a new framework able to deal with a reasoning that is at the same time non monotonic and uncertain. In order to take into account a certainty level associated to each piece of knowledge, we use possibility theory to extend the non monotonic semantics of stable models for logic programs with default negation. By means of a possibility distribution we define a clear semantics of such programs by introducing what is a possibilistic stable model. We also propose a syntactic process based on a fix-point operator to compute these particular models representing the deductions of the program and their certainty. Then, we show how this introduction of a certainty level on each rule of a program can be used in order to restore its consistency in case of the program has no model at all. Furthermore, we explain how we can compute possibilistic stable models by using available softwares for Answer Set Programming and we describe the main lines of the system that we have developed to achieve this goal.     

Analyzing XACML policies using answer set programming

International Journal of Information Security - With the tremendous growth of Web applications and services, eXtensible Access Control Markup Language (XACML) has been broadly adopted to specify...     

On the verification of polynomial system solvers

We discuss the verification of mathematical software solving polynomial systems symbolically by way of triangular decomposition. Standard verification techniques are highly resource consuming and apply only to polynomial systems which are easy to solve. We exhibit a new approach which manipulates constructible sets represented by regular systems. We provide comparative benchmarks of different verification procedures applied to four solvers on a large set of well-known polynomial systems. Our experimental results illustrate the high efficiency of our new approach. In particular, we are able to verify triangular decompositions of polynomial systems which are not easy to solve.     

Integrating answer set programming and constraint logic programming

We introduce a knowledge representation language ${\cal AC(C)}$ extending the syntax and semantics of ASP and CR-Prolog, give some examples of its use, and present an algorithm, $\mathcal{AC}\!solver$ , for computing answer sets of ${\cal AC(C)}$ programs. The algorithm does not require full grounding of a program and combines “classical” ASP solving methods with constraint logic programming techniques and CR-Prolog based abduction. The ${\cal AC(C)}$ based approach often allows to solve problems which are impossible to solve by more traditional ASP solving techniques. We believe that further investigation of the language and development of more efficient and reliable solvers for its programs can help to substantially expand the domain of applicability of the answer set programming paradigm.     

Adjudication of coreference annotations via answer set optimisation

Abstract

We describe the first automatic approach for merging coreference annotations obtained from multiple annotators into a single gold standard. This merging is subject to certain linguistic hard constraints and optimisation criteria that prefer solutions with minimal divergence from annotators. The representation involves an equivalence relation over a large number of elements. We use Answer Set Programming to describe two representations of the problem and four objective functions suitable for different data-sets. We provide two structurally different real-world benchmark data-sets based on the METU-Sabanci Turkish Treebank and we report our experiences in using the Gringo, Clasp and Wasp tools for computing optimal adjudication results on these data-sets.     

析取回答集程序设计结构化测试方法

针对析取回答集程序的结构化测试基础理论匮乏的问题,系统化地提出析取回答集程序结构化测试覆盖的概念。首先,定义针对析取回答集程序的测试用例,确立析取回答集程序的主要测试实体为程序中的逻辑规则;其次,通过对规则的头、规则的体、规则的集合等不同测试目标构建了规则覆盖、定义覆盖、环覆盖等基本概念来模拟结构化测试中的语句覆盖、分支覆盖等概念;最后,提出了析取回答集程序的测试覆盖率计算公式,并举例说明各种覆盖下的覆盖率计算方法,并讨论了析取回答集程序的部分特殊性质和关键指标。     

On the relation between rough set reducts and jumping emerging patterns

This paper presents the relations between rough set reducts and jumping emerging patterns. Observations are introduced formally and supported by brief examples. Furthermore, we propose practical applications of these observations to the minimal reduct problem and to testing whether a given attribute set is differentiating. We believe that our study can be expanded so as to include other types of reducts and emerging patterns.     

Handling distributed authorization with delegation through answer set programming

Distributed authorization is an essential issue in computer security. Recent research shows that trust management is a promising approach for the authorization in distributed environments. There are two key issues for a trust management system: how to design an expressive high-level policy language and how to solve the compliance-checking problem (Blaze et al. in Proceedings of the Symposium on Security and Privacy, pp. 164–173, 1996; Proceedings of 2nd International Conference on Financial Cryptography (FC’98). LNCS, vol.1465, pp. 254–274, 1998), where ordinary logic programming has been used to formalize various distributed authorization policies (Li et al. in Proceedings of the 2002 IEEE Symposium on Security and Privacy, pp. 114–130, 2002; ACM Trans. Inf. Syst. Secur. (TISSEC) 6(1):128–171, 2003). In this paper, we employ Answer Set Programming to deal with many complex issues associated with the distributed authorization along the trust management approach. In particular, we propose a formal authorization language providing its semantics through Answer Set Programming. Using language , we cannot only express nonmonotonic delegation policies which have not been considered in previous approaches, but also represent the delegation with depth, separation of duty, and positive and negative authorizations. We also investigate basic computational properties related to our approach. Through two case studies. we further illustrate the application of our approach in distributed environments.     

On designing optimal parallel triangular solvers

This paper explores the problem of solving triangular linear systems on parallel distributed-memory machines. Working within the LogP model, tight asymptotic bounds for solving these systems using forward/backward substitution are presented. Specifically, lower bounds on execution time independent of the data layout, lower bounds for data layouts in which the number of data items per processor is bounded, and lower bounds for specific data layouts commonly used in designing parallel algorithms for this problem are presented in this paper. Furthermore, algorithms are provided which have running times within a constant factor of the lower bounds described. One interesting result is that the popular two-dimensional block matrix layout necessarily results in significantly longer running times than simpler one-dimensional schemes. Finally, a generalization of the lower bounds to banded triangular linear systems is presented.     

On some parallel banded system solvers

This paper describes algorithms for solving narrow banded systems and the Helmholtz difference equations that are suitable for multiprocessing systems. The organization of the algorithms highlight the large grain parallelism inherent in the problems.     

Semantics and complexity of recursive aggregates in answer set programming

The addition of aggregates has been one of the most relevant enhancements to the language of answer set programming (ASP). They strengthen the modelling power of ASP in terms of natural and concise problem representations. Previous semantic definitions typically agree in the case of non-recursive aggregates, but the picture is less clear for aggregates involved in recursion. Some proposals explicitly avoid recursive aggregates, most others differ, and many of them do not satisfy desirable criteria, such as minimality or coincidence with answer sets in the aggregate-free case.In this paper we define a semantics for programs with arbitrary aggregates (including monotone, antimonotone, and nonmonotone aggregates) in the full ASP language allowing also for disjunction in the head (disjunctive logic programming — DLP). This semantics is a genuine generalization of the answer set semantics for DLP, it is defined by a natural variant of the Gelfond–Lifschitz transformation, and treats aggregate and non-aggregate literals in a uniform way. This novel transformation is interesting per se also in the aggregate-free case, since it is simpler than the original transformation and does not need to differentiate between positive and negative literals. We prove that our semantics guarantees the minimality (and therefore the incomparability) of answer sets, and we demonstrate that it coincides with the standard answer set semantics on aggregate-free programs.Moreover, we carry out an in-depth study of the computational complexity of the language. The analysis pays particular attention to the impact of syntactical restrictions on programs in the form of limited use of aggregates, disjunction, and negation. While the addition of aggregates does not affect the complexity of the full DLP language, it turns out that their presence does increase the complexity of normal (i.e., non-disjunctive) ASP programs up to the second level of the polynomial hierarchy. However, we show that there are large classes of aggregates the addition of which does not cause any complexity gap even for normal programs, including the fragment allowing for arbitrary monotone, arbitrary antimonotone, and stratified (i.e., non-recursive) nonmonotone aggregates. The analysis provides some useful indications on the possibility to implement aggregates in existing reasoning engines.     

Dealing with explicit preferences and uncertainty in answer set programming

In this paper, we show how the formalism of Logic Programs with Ordered Disjunction (LPODs) and Possibilistic Answer Set Programming (PASP) can be merged into the single framework of Logic Programs with Possibilistic Ordered Disjunction (LPPODs). The LPPODs framework embeds in a unified way several aspects of common-sense reasoning, nonmonotonocity, preferences, and uncertainty, where each part is underpinned by a well established formalism. On one hand, from LPODs it inherits the distinctive feature of expressing context-dependent qualitative preferences among different alternatives (modeled as the atoms of a logic program). On the other hand, PASP allows for qualitative certainty statements about the rules themselves (modeled as necessity values according to possibilistic logic) to be captured. In this way, the LPPODs framework supports a reasoning which is nonmonotonic, preference- and uncertainty-aware. The LPPODs syntax allows for the specification of (1) preferences among the exceptions to default rules, and (2)?necessity values about the certainty of program rules. As a result, preferences and uncertainty can be used to select the preferred uncertain default rules of an LPPOD and, consequently, to order its possibilistic answer sets. Furthermore, we describe the implementation of an ASP-based solver able to compute the LPPODs semantics.     

On parallel solvers for sparse triangular systems

In this paper we describe and compare two different methods for solving general sparse triangular systems in distributed memory multiprocessor architectures. The two methods involve some preprocessing overheads so they are primarily of interest in solving many systems with the same coefficient matrix. Both algorithms start off from the idea of the classical substitution method. The first algorithm we present introduces a concept of data driven flow and makes use of non-blocking communications in order to dynamically extract the inherent parallelism of sparse systems. The second algorithm uses a reordering technique for the unknowns, so the final system can be grouped in variable blocksizes where the rows are independent and can be solved in parallel. This latter technique is called level scheduling because of the way it is represented in the adjacency graph. These methods have been tested in the Fujitsu AP1000 and the Cray T3D and T3E multicomputers. The performance has been analysed using matrices from the Harwell-Boeing collection.     

Inductive learning of answer set programs for autonomous surgical task planning

Machine Learning - The quality of robot-assisted surgery can be improved and the use of hospital resources can be optimized by enhancing autonomy and reliability in the robot’s operation....