Intentional forgetting means to deliberately give up information and is a crucial part of change or consolidation processes, or to make knowledge more compact. Two well-known forgetting operations are contraction in t...
详细信息
ISBN:
(纸本)9783030299088;9783030299071
Intentional forgetting means to deliberately give up information and is a crucial part of change or consolidation processes, or to make knowledge more compact. Two well-known forgetting operations are contraction in the AGM theory of belief change, and various types of variable elimination in logic programming. While previous work dealt with postulates being inspired from logic programming, in this paper we focus on evaluating forgetting in epistemic states according to postulates coming from AGM belief change theory. We consider different forms of contraction, marginalization, and conditionalization as major representatives of forgetting operators to be evaluated. We use Spohn's ranking functions as a common semantic base to show that all operations can be realized in one logical framework, thereby exploring the richness of forgetting operations in a comparable way.
It is now widely accepted that the operation of forgetting in the context of Answer Set programming [10,18] is best characterized by the so-called strong persistence, a property that requires that all existing relatio...
详细信息
ISBN:
(纸本)9783030302443;9783030302436
It is now widely accepted that the operation of forgetting in the context of Answer Set programming [10,18] is best characterized by the so-called strong persistence, a property that requires that all existing relations between the atoms not to be forgotten be preserved. However, it has been shown that strong persistence cannot always be satisfied. What happens if we must nevertheless forget? One possibility that has been explored before is to consider weaker versions of strong persistence, although not without a cost: some relations between the atoms not to be forgotten are broken in the process. A different alternative is to enhance the logical language so that all such relations can be maintained after the forgetting operation. In this paper, we borrow from the recently introduced notion of fork [1] - a conservative extension of Equilibrium logic and its monotonic basis, the logic of Here-and-There - which has been shown to be sufficient to overcome the problems related to satisfying strong persistence. We map this notion into the language of logic programs, enhancing it with so-called anonymous cycles, and we introduce a concrete syntactical forgetting operator over this enhanced language that we show to always obey strong persistence.
Property-based testing (PBT) is a technique for validating code against an executable specification by automatically generating test-data. We present a proof-theoretical reconstruction of this style of testing for rel...
详细信息
ISBN:
(纸本)9781450372497
Property-based testing (PBT) is a technique for validating code against an executable specification by automatically generating test-data. We present a proof-theoretical reconstruction of this style of testing for relational specifications and employ the Foundational Proof Certificate framework to describe test generators. We do this by presenting certain kinds of "proof outlines" that can be used to describe various common generation strategies in the PBT literature, ranging from random to exhaustive, including their combination. We also address the shrinking of counterexamples as a first step towards their explanation. Once generation is accomplished, the testing phase boils down to a standard logic programming search. After illustrating our techniques on simple, first-order (algebraic) data structures, we lift it to data structures containing bindings using.-tree syntax. The lambda Prolog programming language is capable of performing both the generation and checking of tests. We validate this approach by tackling benchmarks in the metatheory of programming languages coming from related tools such as PLT-Redex.
Database Reformulation is the process of rewriting the data and rules in deductive databases in a functionally equivalent manner, ideally in ways that decrease query processing time while keeping storage costs within ...
详细信息
ISBN:
(纸本)9781728114880
Database Reformulation is the process of rewriting the data and rules in deductive databases in a functionally equivalent manner, ideally in ways that decrease query processing time while keeping storage costs within acceptable bounds. Early research in this area focussed on materializing existing views, i.e. caching those views as data. Subsequent research investigated the problem of inventing new views to afford different opportunities for materialization. The Bounding Theorem, introduced in this latter effort, is significant in that it gives a finite bound on the number of useful reformulations for conjunctive queries. Unfortunately, the number of possibilities allowed by the Bounding Theorem is doubly exponential in the size of the query (not the database instance). In this paper, we show that we can reduce that double exponential to a single exponential. We first present an improved version of the Bounding Theorem, called the Subgoal Theorem. We then present an additional result, called the Projection Theorem. Finally, we present a reformulation algorithm that runs in exponential time;and, using the Subgoal Theorem and the Projection Theorem, we show that the algorithm is correct for all conjunctive queries, i.e. it produces reformulations that are as good as or better than any other reformulation (in terms of worst-case query evaluation performance with at most linear growth in storage space).
Epistemic logic Programs (ELPs), that is, Answer Set programming (ASP) extended with epistemic operators, have received renewed interest in recent years, which led to a flurry of new research, as well as efficient sol...
详细信息
ISBN:
(纸本)9781577358091
Epistemic logic Programs (ELPs), that is, Answer Set programming (ASP) extended with epistemic operators, have received renewed interest in recent years, which led to a flurry of new research, as well as efficient solvers. An important question is under which conditions a sub-program can be replaced by another one without changing the meaning, in any context. This problem is known as strong equivalence, and is well-studied for ASP. For ELPs, this question has been approached by embedding them into epistemic extensions of equilibrium logics. In this paper, we consider a simpler, more direct characterization that is directly applicable to the language used in state-of-the-art ELP solvers. This also allows us to give tight complexity bounds, showing that strong equivalence for ELPs remains coNP-complete, as for ASP. We further use our results to provide syntactic characterizations for tautological rules and rule subsumption for ELPs.
Now, and in the times that follow, student education should focus on developing inclusive skills such as problem-solving and decision-making, where the role of the learning environment plays a crucial part, i.e., it i...
详细信息
ISBN:
(纸本)9783319988726;9783319988719
Now, and in the times that follow, student education should focus on developing inclusive skills such as problem-solving and decision-making, where the role of the learning environment plays a crucial part, i.e., it is a process where the screen of the universe of discourse is accomplished in order to consider not only the complex relationships that flow among the objects that populate it, but also its inner structure, co-existing incomplete/unknown or even self-contradictory information or knowledge. As a result, we will focus on the development of an Intelligent Social Machine to assess Learning Environments in high schools, based on factors like School and Disciplinary Climates as well as Parental Involvement. The formal background will be to use logic programming to define its architecture based on a Deep Learning-Big Data approach to Knowledge Representation and Reasoning, complemented by an Evolutionary approach to Computing grounded on Virtual Intellects.
We address the issue of abstraction, a widely used notion to simplify problems, in the context of Answer Set programming (ASP), which is a highly expressive formalism and a convenient tool for declarative problem solv...
详细信息
ISBN:
(纸本)9783030195700;9783030195694
We address the issue of abstraction, a widely used notion to simplify problems, in the context of Answer Set programming (ASP), which is a highly expressive formalism and a convenient tool for declarative problem solving. We introduce a method to automatically abstract non-ground ASP programs given an abstraction over the domain, which ensures that each original answer set is mapped to some abstract answer set. We discuss abstraction possibilities on several examples and show the use of abstraction to gain insight into problem instances, e.g., domain details irrelevant for problem solving;this makes abstraction attractive for getting to the essence of the problem. We also provide a tool implementing automatic abstraction from an input program.
Assumption-based argumentation is one of the most prominent formalisms for logical (or structured) argumentation. It has been shown useful for representing defeasible reasoning and has tight links to logic programming...
详细信息
ISBN:
(纸本)9783030205287;9783030205270
Assumption-based argumentation is one of the most prominent formalisms for logical (or structured) argumentation. It has been shown useful for representing defeasible reasoning and has tight links to logic programming In this paper we study the Dung semantics for extended forms of assumption-based argumentation frameworks (ABFs), based on any contrapositive propositional logic, and whose defeasible rules are expressed by arbitrary formulas in that logic. In particular, new results on the well-founded semantics for such ABFs are reported, the redundancy of the closure condition is shown, and the use of disjunctive attacks is investigated. Finally, some useful properties of the generalized frameworks are considered.
We present a system for online, incremental composite event recognition. In streaming environments, the usual case is for data to arrive with a (variable) delay from, and to be retracted/revised by the underlying sour...
详细信息
ISBN:
(纸本)9781450367943
We present a system for online, incremental composite event recognition. In streaming environments, the usual case is for data to arrive with a (variable) delay from, and to be retracted/revised by the underlying sources. We propose RTECinc, an incremental version of RTEC, a composite event recognition engine with a formal, declarative semantics, that has been shown to scale to several real-world data streams. RTEC deals with delayed arrival and retraction of events by computing at each query time composite event intervals from scratch. This often results to redundant computations. Instead, RTECinc deals with delays and retractions in a more efficient way, by updating only the affected events. We evaluate RTECinc theoretically, presenting a complexity analysis, and show the conditions in which it outperforms RTEC. Moreover, we compare RTECinc and RTEC experimentally using two real-world datasets. The results are compatible with our theoretical analysis and show that RTECinc may outperform RTEC.
Internet routing is the process of selecting paths across the Internet to connect the communicating hosts, it is unique in that path selection is jointly determined by a network of independently operated networks, kno...
详细信息
ISBN:
(纸本)9783030205287;9783030205270
Internet routing is the process of selecting paths across the Internet to connect the communicating hosts, it is unique in that path selection is jointly determined by a network of independently operated networks, known as domains or Autonomous Systems (ASes), that interconnect to form the Internet. In fact, the present routing infrastructure takes such an extreme position that it favors local autonomy-an AS can use arbitrary path preference to override the default shortest path policy, at the expense of potential global oscillation-a collection of AS preferences (policies) can fail to converge on a stable path, a path that is also the most preferred possible for every AS along the path. In this paper, we examine the route oscillation problem with non-monotonic reasoning. We observe that, in the absence of any AS specific policies, Internet routing degenerates into the monotonic computation of shortest path-a preferred (shorter) (super)path always extends another preferred (sub)path;But fully autonomous AS policies are non-monotonic a path favored by one AS can be an extension of a less preferred path of a neighbor, to which an "upgrade" to a better path can cause this AS to downgrade to a less preferred path previously discarded. Based on this insight, we present an Answer Set programming (ASP) formulation that allows for automatic oscillation detection. Our evaluation using the clingo ASP solver is promising: on realistic Internet topology and representative policies, clingo can detect anomalies within 35 s.
暂无评论