answer set programming (ASP) solvers are highly-tuned and complex procedures that implicitly solve the consistency problem, i.e., deciding whether a logic program admits an answerset. Verifying whether a claimed answ...
详细信息
answer set programming (ASP) solvers are highly-tuned and complex procedures that implicitly solve the consistency problem, i.e., deciding whether a logic program admits an answerset. Verifying whether a claimed answerset is formally a correct answerset of the program can be decided in polynomial time for (normal) programs. However, it is far from immediate to verify whether a program that is claimed to be inconsistent, indeed does not admit any answersets. In this paper, we address this problem and develop the new proof format ASP-DRUPE for propositional, disjunctive logic programs, including weight and choice rules. ASP-DRUPE is based on the Reverse Unit Propagation (RUP) format designed for Boolean satisfiability. We establish correctness of ASP-DRUPE and discuss how to integrate it into modern ASP solvers. Later, we provide an implementation of ASP-DRUPE into the wasp solver for normal logic programs.
In the theory of answer set programming, two groups of rules are called strongly equivalent if, informally speaking, they have the same meaning in any context. The relationship between strong equivalence and the propo...
详细信息
In the theory of answer set programming, two groups of rules are called strongly equivalent if, informally speaking, they have the same meaning in any context. The relationship between strong equivalence and the propositional logic of here-and-there allows us to establish strong equivalence by deriving rules of each group from rules of the other. In the process, rules are rewritten as propositional formulas. We extend this method of proving strong equivalence to an answer set programming language that includes operations on integers. The formula representing a rule in this language is a first-order formula that may contain comparison symbols among its predicate constants, and symbols for arithmetic operations among its function constants. The paper is under consideration for acceptance in TPLP.
The increasing availability of streaming data has accelerated advances in information processing tools that no longer store data for static querying but push information to consumers as soon as it becomes available. S...
详细信息
The increasing availability of streaming data has accelerated advances in information processing tools that no longer store data for static querying but push information to consumers as soon as it becomes available. Stream processing aims at providing languages and tools for data that changes at a high rate. To cope with the volume of data, query languages often extend existing approaches for static data by means of window operators that return snapshots of recent data. However, the semantics of these languages are often given only informally or operationally, which makes their analysis and comparison difficult. A formal means to express the declarative semantics of such systems seems to be missing. This lack of theory is of particular relevance for the emerging research in stream reasoning which shifts the focus from throughput to higher expressiveness. To fill this gap, we present LARS, a Logic-based framework for Analytic Reasoning over Streams. At its core, LARS formulas extend propositional logic with generic window operators and additional controls to handle temporal information. On top of this, LARS programs extend answer set programming (ASP) with rich stream reasoning capabilities;the latter can be exploited to target Al applications in a streaming context, such as diagnosis, configuration or planning. Specifically, we study in this article the computational complexity of LARS formulas and programs, their relationship to Linear Temporal Logic (LTL) and the well-known Continuous Query Language (CQL). Furthermore, we discuss the modeling capabilities of LARS in notes on the SPARQL extensions C-SPARQL and CQELS, and on the interval-based approach of the complex event processing language ETALIS. We finally briefly touch available implementations, in particular, the recent prototype engines Laser and Ticker that aim for high throughput and high expressiveness, respectively. Notably, both engines specify their semantics in LARS, indicating the desired flexibility
Fuzzy answer set programming (FASP) combines two declarative frameworks, answer set programming and fuzzy logic, in order to model reasoning by default over imprecise information. Several connectives are available to ...
详细信息
Fuzzy answer set programming (FASP) combines two declarative frameworks, answer set programming and fuzzy logic, in order to model reasoning by default over imprecise information. Several connectives are available to combine different expressions;in particular the Godel and Lukasiewicz fuzzy connectives are usually considered, due to their properties. Although the Godel conjunction can be easily eliminated from rule heads, we show through complexity arguments that such a simplification is infeasible in general for all other connectives. The paper analyzes a translation of FASP programs into satisfiability modulo theories (SMT), which in general produces quantified formulas because of the minimality of the semantics. Structural properties of many FASP programs allow to eliminate the quantification, or to sensibly reduce the number of quantified variables. Indeed, integrality constraints can replace recursive rules commonly used to force Boolean interpretations, and completion subformulas can guarantee minimality for acyclic programs with atomic heads. Moreover, head cycle free rules can be replaced by shifted subprograms, whose structure depends on the eliminated head connective, so that ordered completion may replace the minimality check if also Lukasiewicz disjunction in rule bodies is acyclic. The paper also presents and evaluates a prototype system implementing these translations.
Information diffusion is a classical problem in social network analysis, which has been largely investigated with reference to single social networks. However, the current scenario is multi-social-network. Here, many ...
详细信息
Information diffusion is a classical problem in social network analysis, which has been largely investigated with reference to single social networks. However, the current scenario is multi-social-network. Here, many social networks coexist and are strictly connected to each other, thanks to those users who join more social networks, acting as bridges among them. But, what happens to information diffusion when passing from a single-social-network context to a multi-social-network scenario? In this paper, we answer this question. In particular, thanks to the definition of a framework for handling these issues and to a large set of experiments, we show that, in this context, new actors and new features play the key roles. We also identify two possible improvements of our framework, namely the management of some "activation nucleuses" (i.e., some starting-node configurations that are likely to improve information diffusion) and the management of topics concerning the information to spread. In these activities, answer set programming provided us with a powerful and flexible tool for an easy setup and implementation of our investigation.
In the last years, abstract argumentation has met with great success in AI, since it has served to capture several non-monotonic logics for AI. Relations between argumentation framework (AF) semantics and logic progra...
详细信息
In the last years, abstract argumentation has met with great success in AI, since it has served to capture several non-monotonic logics for AI. Relations between argumentation framework (AF) semantics and logic programming ones are investigating more and more. In particular, great attention has been given to the well-known stable extensions of an AF, that are closely related to the answersets of a logic program. However, if a framework admits a small incoherent part, no stable extension can be provided. To overcome this shortcoming, two semantics generalizing stable extensions have been studied, namely semi-stable and stage. In this paper, we show that another perspective is possible on incoherent AFs, called paracoherent extensions, as they have a counterpart in paracoherent answerset semantics. We compare this perspective with semi-stable and stage semantics, by showing that computational costs remain unchanged, and moreover an interesting symmetric behaviour is maintained.
In this paper, a possibilistic disjunctive logic programming approach for modeling uncertain, incomplete, and inconsistent information is defined. This approach introduces the use of possibilistic disjunctive clauses,...
详细信息
In this paper, a possibilistic disjunctive logic programming approach for modeling uncertain, incomplete, and inconsistent information is defined. This approach introduces the use of possibilistic disjunctive clauses, which are able to capture incomplete information and states of a knowledge base at the same time. By considering a possibilistic logic program as a possibilistic logic theory, a construction of a possibilistic logic programming semantic based on answersets and the proof theory of possibilistic logic is defined. It shows that this possibilistic semantics for disjunctive logic programs can be characterized by a fixed-point operator. It is also shown that the suggested possibilistic semantics can be computed by a resolution algorithm and the consideration of optimal refutations from a possibilistic logic theory. In order to manage inconsistent possibilistic logic programs, a preference criterion between inconsistent possibilistic models is defined. In addition, the approach of cuts for restoring consistency of an inconsistent possibilistic knowledge base is adopted. The approach is illustrated in a medical scenario.
answerset programs used in real-world applications often require that the program is usable with different input data. This, however, can often lead to contradictory statements and consequently to an inconsistent pro...
详细信息
answerset programs used in real-world applications often require that the program is usable with different input data. This, however, can often lead to contradictory statements and consequently to an inconsistent program. Causes for potential contradictions in a program are conflicting rules. In this paper, we show how to ensure that a program P remains non-contradictory given any allowed set of such input data. For that, we introduce the notion of conflict-resolving lambda-extensions. A conflict-resolving lambda-extension for a conflicting rule r is a set lambda of (default) literals such that extending the body of r by lambda resolves all conflicts of r at once. We investigate the properties that suitable lambda-extensions should possess and building on that, we develop a strategy to compute all such conflict-resolving lambda-extensions for each conflicting rule in P. We show that by implementing a conflict resolution process that successively resolves conflicts using lambda-extensions eventually yields a program that remains non-contradictory given any allowed set of input data.
We investigate the problem of cost-optimal planning in ASP. Current ASP planners can be trivially extended to a cost-optimal one by adding weak constraints, but only for a given makespan (number of steps). It is desir...
详细信息
We investigate the problem of cost-optimal planning in ASP. Current ASP planners can be trivially extended to a cost-optimal one by adding weak constraints, but only for a given makespan (number of steps). It is desirable to have a planner that guarantees global optimality. In this paper, we present two approaches to addressing this problem. First, we show how to engineer a cost-optimal planner composed of two ASP programs running in parallel. Using lessons learned from this, we then develop an entirely new approach to cost-optimal planning, stepless planning, which is completely free of makespan. Experiments to compare the two approaches with the only known cost-optimal planner in SAT reveal good potentials for stepless planning in ASP.
In a recent line of research, two familiar concepts from logic programming semantics (unfounded sets and splitting) were extrapolated to the case of epistemic logic programs. The property of epistemic splitting provid...
详细信息
In a recent line of research, two familiar concepts from logic programming semantics (unfounded sets and splitting) were extrapolated to the case of epistemic logic programs. The property of epistemic splitting provides a natural and modular way to understand programs without epistemic cycles but, surprisingly, was only fulfilled by Gelfond's original semantics (G91), among the many proposals in the literature. On the other hand, G91 may suffer from a kind of self-supported, unfounded derivations when epistemic cycles come into play. Recently, the absence of these derivations was also formalised as a property of epistemic semantics called foundedness. Moreover, a first semantics proved to satisfy foundedness was also proposed, the so-called Founded Autoepistemic Equilibrium Logic (FAEEL). In this paper, we prove that FAEEL also satisfies the epistemic splitting property something that, together with foundedness, was not fulfilled by any other approach up to date. To prove this result, we provide an alternative characterisation of FAEEL as a combination of G91 with a simpler logic we called Founded Epistemic Equilibrium Logic (FEEL), which is somehow an extrapolation of the stable model semantics to the modal logic S5.
暂无评论