In answer set programming systems like Smodels and some SAT solvers, constraint propagation is carried out by a mechanism called lookahead. the question arises as what is the pruning power of lookahead, and how such p...
详细信息
ISBN:
(纸本)3540285385
In answer set programming systems like Smodels and some SAT solvers, constraint propagation is carried out by a mechanism called lookahead. the question arises as what is the pruning power of lookahead, and how such pruning power fares in comparison withthe consistency techniques in solving CSPs. In this paper, we study the pruning power of lookahead by relating it to local consistencies under two different encodings from CSPs to answer set programs. this leads to an understanding of how the search space is pruned in an answer set solver with lookahead for solving CSPs. On the other hand, lookahead as a general constraint propagation mechanism provides a uniform algorithm for enforcing a variety of local consistencies. We also study the impact on the search efficiency under these encodings.
Brewka and Eiter's nonmonotonic multi-context system is an elegant knowledge representation framework to model heterogeneous and nonmonotonic multiple contexts. Belief change is a central problem in knowledge repr...
详细信息
ISBN:
(纸本)9783642405648
Brewka and Eiter's nonmonotonic multi-context system is an elegant knowledge representation framework to model heterogeneous and nonmonotonic multiple contexts. Belief change is a central problem in knowledge representation and reasoning. In this paper we follow the classical AGM approach to investigate belief change in multi-context systems. Specifically, we formulate semantically the AGM postulates of belief expansion, revision and contraction for multi-context systems. We show that the change operations can be characterized in terms of minimal change by ordering equilibria of multi-context systems. Two distance based revision operators are obtained and related to the classical Satoh and Dalal revision operators (via loop formulas).
Configurable on chip multiprocessor systems combine advantages of task-level parallelism and the flexibility Of field-programmable devices to customize architectures for parallel programs, thereby alleviating technolo...
详细信息
ISBN:
(纸本)9783642042379
Configurable on chip multiprocessor systems combine advantages of task-level parallelism and the flexibility Of field-programmable devices to customize architectures for parallel programs, thereby alleviating technological limitations due to memory bandwidth and power Consumption. Given the huge size of the design Space Of Such Systems, it is important to automatically optimize design parameters in order to facilitate wide and disciplined explorations. Being a combinatorial problem. system design can be modeled and solved as Such, but the amount of parameters renders the problem difficult to Solve for large instances. However. its the synthesis problem usually exhibits structure, Answer Set programming (ASP), for which solvers utilizing techniques from the propositional satisfiability domain are available, can be effectively employed. this paper presents a design flow based on ASP that uses the solver clasp as back-end engine. Synthesis experiments demonstrate the effectiveness of the approach.
In this paper we define a semantic foundation for an abstract interpretation approach to universal termination and we develop a new abstract domain useful for termination analysis. Based on this approximation we defin...
详细信息
ISBN:
(纸本)3540412859
In this paper we define a semantic foundation for an abstract interpretation approach to universal termination and we develop a new abstract domain useful for termination analysis. Based on this approximation we define a method which is able to detect classes of goals which universally terminate (with a fair selection rule). We also define a method which is able to characterize classes of programs and goals for which depth-first search is fair.
We present a new logicprogramming approach to contextual reasoning, based on the Weak Completion Semantics (WCS), the latter of which has been successfully applied in the past to adequately model various human reason...
详细信息
ISBN:
(纸本)9783319616605;9783319616599
We present a new logicprogramming approach to contextual reasoning, based on the Weak Completion Semantics (WCS), the latter of which has been successfully applied in the past to adequately model various human reasoning tasks. One of the properties of WCS is the open world assumption with respect to undefined atoms. this is a characteristic that is different to other common logicprogramming semantics, a property that seems suitable when modeling human reasoning. Notwithstanding, we have noticed that the famous Tweety default reasoning example, originally introduced by Reiter, cannot be modeled straightforwardly under WCS. Hence, to address the issue and taking Pereira and Pinto's inspection points as inspiration, we develop a notion of contextual reasoning for which we introduce contextual logic programs. We reconsider the formal properties of WCS with respect to these and verify whether they still hold. Finally, we set forth contextual abduction and show that not only the original Tweety example can be nicely modeled within the new approach, but more sophisticated examples as well, where context plays an important role.
We describe the first automatic approach for merging coreference annotations obtained from multiple annotators into a single gold standard. Merging is subject to hard constraints (consistency) and optimization criteri...
详细信息
ISBN:
(纸本)9783319616605;9783319616599
We describe the first automatic approach for merging coreference annotations obtained from multiple annotators into a single gold standard. Merging is subject to hard constraints (consistency) and optimization criteria (minimal divergence from annotators) and involves an equivalence relation over a large number of elements. We describe two representations of the problem in Answer Set programming and four objective functions suitable for the task. We provide two structurally different real-world benchmark datasets 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 datasets.
Heterogeneous nonmonotonic multi-context systems (MCS) permit different logics to be used in different contexts, and link them via bridge rules. We investigate the role of symmetry detection and symmetry breaking in s...
详细信息
ISBN:
(纸本)9783642208942;9783642208959
Heterogeneous nonmonotonic multi-context systems (MCS) permit different logics to be used in different contexts, and link them via bridge rules. We investigate the role of symmetry detection and symmetry breaking in such systems to eliminate symmetric parts of the search space and, thereby, simplify the evaluation process. We propose a distributed algorithm that takes a local stance, i.e., computes independently the partial symmetries of a context and, in order to construct potential symmetries of the whole, combines them withthose partial symmetries returned by neighbouring contexts. We prove the correctness of our methods. We instantiate such symmetry detection and symmetry breaking in a multi-context system with contexts that use answer set programs, and demonstrate computational benefit on some recently proposed benchmarks.
Intensional logicprogramming is an extension of logicprogramming based on intensional logic, which includes as special cases both temporal and modal logicprogramming. In [OW92], M. Orgun and W. W. Wadge provided a ...
详细信息
ISBN:
(纸本)9783642405648
Intensional logicprogramming is an extension of logicprogramming based on intensional logic, which includes as special cases both temporal and modal logicprogramming. In [OW92], M. Orgun and W. W. Wadge provided a general framework for capturing the semantics of intensional logicprogramming languages. One key property involved in the construction of [OW92], is the monotonicity of intensional operators. In this paper we consider intensional logicprogramming from a game-theoretic perspective. In particular we define a two-person game and we demonstrate that it is equivalent to the semantics of [OW92]. More importantly, we demonstrate that the game is even applicable to intensional languages with non-monotonic operators. In this way we provide the first (to our knowledge) general semantic framework for capturing the semantics of non-monotonic intensional logicprogramming.
Recent research in nonmonotoniclogicprogramming under the answer-set semantics focuses on different notions of program equivalence. However, previous results do not address the important classes of stratified progra...
详细信息
Recent research in nonmonotoniclogicprogramming under the answer-set semantics focuses on different notions of program equivalence. However, previous results do not address the important classes of stratified programs and its subclass of acyclic (i.e., recursion-free) programs, although they are recognized as important tools for knowledge representation and reasoning. In this paper, we consider such programs, possibly augmented with constraints. Our results show that in the propositional setting, where reasoning is well-known to be polynomial, deciding strong and uniform equivalence is as hard as for arbitrary normal logic programs (and thus coNP-complete), but is polynomial in some restricted cases. Non-ground programs behave similarly. However, exponential lower bounds already hold for small programs (i.e., with constantly many rules). In particular, uniform equivalence is undecidable even for small Horn programs plus a single negative constraint.
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 paththat 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.
暂无评论