the description logic SHI extends the basic description logic ALC with transitive roles, role hierarchies and inverse roles. the known tableau-based decision procedure [9] for SHI exhibit (at least) NEXP-TIME behaviou...
详细信息
ISBN:
(纸本)9783540730989
the description logic SHI extends the basic description logic ALC with transitive roles, role hierarchies and inverse roles. the known tableau-based decision procedure [9] for SHI exhibit (at least) NEXP-TIME behaviour even though SHI is known to be EXPTIME-complete. the automata-based algorithms for SHI often yield optimal worst-case complexity results, but do not behave well in practice since good optimisations for them have yet to be found. We extend our method for global caching in ALC to SHI by adding analytic cut rules, thereby giving the first EXPTIME tableau-based decision procedure for SHI, and showing one way to incorporate global caching and inverse roles.
this paper discusses the argumentative reasoning methodology adopted during knowledge sharing and the special techniques utilized from Indian logic to reason with inconsistent knowledge. Winning or losing arguments ar...
详细信息
ISBN:
(纸本)9780769530505
this paper discusses the argumentative reasoning methodology adopted during knowledge sharing and the special techniques utilized from Indian logic to reason with inconsistent knowledge. Winning or losing arguments are not important;the amount of valid information shared between the arguers during rational debate qualifies for the scope of discussion. Proponent's arguments explain one's thoughts or beliefs to the opponent. the knowledge shared by the proponent may be invalid or inconsistent with respect to the opponent's common sense knowledge. therefore, the opponent reverts rationally through a counter argument. the proponent then removes the contradictions and proposes subsequent argument to the opponent. this exchange of propositions or arguments continues until the participant(s) is convinced about the shared knowledge. the validity of the shared knowledge shall be evaluated by measuring the components of the participants knowledge base.
We present a purely model-theoretic semantics for disjunctive logic programs with negation, building on the infinite-valued approach recently introduced for normal logic programs [9]. In particular, we show that every...
详细信息
ISBN:
(纸本)9783540721994
We present a purely model-theoretic semantics for disjunctive logic programs with negation, building on the infinite-valued approach recently introduced for normal logic programs [9]. In particular, we show that every disjunctive logic program with negation has a non-empty set of minimal infinite-valued models. Moreover, we show that the infinite-valued semantics can be equivalently defined using Kripke models, allowing us to prove some properties of the new semantics more concisely. In particular, for programs without negation, the new approach collapses to the usual minimal model semantics, and when restricted to normal logic programs, it collapses to the well-founded semantics. Lastly, we show that every (propositional) program has a finite set of minimal infinite-valued models which can be identified by restricting attention to a finite subset of the truth values of the underlying logic.
It has been recognised that better programming tools are required to support the logicprogramming paradigm of Answer Set programming (ASP), especially when larger scale applications need to be developed. In order to ...
详细信息
It has been recognised that better programming tools are required to support the logicprogramming paradigm of Answer Set programming (ASP), especially when larger scale applications need to be developed. In order to meet this demand, the aspects of programming in ASP that require better support need to be investigated, and suitable tools to support them identified and implemented. In this paper we detail an exploratory development approach to implementing an Integrated Development Environment (IDE) for ASP, the AnsProlog* programming Environment (APE). APE is implemented as a plug-in for the Eclipse platform. Given that an IDE is itself composed of a set of programming tools, this approach is used to identify a set of tool requirements for ASP, together with suggestions for improvements to existing tools and programming practices.
Competitive native solvers for Answer Set programming (ASP) perform a backtracking search by assuming the truth of literals. the choice of literals (the heuristic) is fundamental for the performance of these systems. ...
详细信息
ISBN:
(纸本)9783540721994
Competitive native solvers for Answer Set programming (ASP) perform a backtracking search by assuming the truth of literals. the choice of literals (the heuristic) is fundamental for the performance of these systems. Most of the efficient ASP systems employ a heuristic based on look-ahead, that is, a literal is tentatively assumed and its heuristic value is based on its deterministic consequences. However, looking ahead is a costly operation, and indeed look-ahead often accounts for the majority of time taken by ASP solvers. For Satisfiability (SAT), a radically different approach, called look-back heuristic, proved to be quite successful: Instead of looking ahead, one uses information gathered during the computation performed so far, thus looking back. In this approach, atoms which have been frequently involved in inconsistencies are preferred. In this paper, we carry over this approach to the framework of disjunctive ASP. We design a number of look-back heuristics exploiting peculiarities of ASP and implement them in the ASP system DLV. We compare their performance on a collection of hard ASP programs both structured and randomly generated. these experiments indicate that a very basic approach works well, outperforming all of the prominent disjunctive ASP systems - DLV (with its traditional heuristic), GnT, and CModels3 - on many of the instances considered.
the paradigm of argumentation has been used in the literature to assign meaning to knowledge bases in general, and logic programs in particular. Withthis paradigm, rules of a logic program are viewed as encoding argu...
详细信息
ISBN:
(纸本)9783540696186
the paradigm of argumentation has been used in the literature to assign meaning to knowledge bases in general, and logic programs in particular. Withthis paradigm, rules of a logic program are viewed as encoding arguments of an agent, and the meaning of the program is determined by those arguments that somehow (depending on the specific semantics) can defend themselves from the attacks of other arguments. Most of the work on argumentation-based logic programs semantics has focused on assigning meaning to single programs. In this paper we propose an argumentation-based negotiation semantics for distributed knowledge bases represented as extended logic programs that extends the existing ones by considering sets of (distributed) logic programs, rather than single ones. For specifying the ways in which the various logic programs may combine their knowledge we make use of concepts that had been developed in the areas of defeasible reasoning, distributed knowledge bases, and multi-agent setting. In particular, we associate to each program P a cooperation set (the set of programs that can be used to complete the knowledge in P) and the argumentation set (the set of programs with which P has to reach a consensus).
Answer-set programming (ASP) has become an important paradigm for declarative problem solving in recent years. However, to further improve the usability of answer-set programs, the development of software-engineering ...
详细信息
ISBN:
(纸本)9783540721994
Answer-set programming (ASP) has become an important paradigm for declarative problem solving in recent years. However, to further improve the usability of answer-set programs, the development of software-engineering tools is vital. In particular, the area of debugging provides a challenge in boththeoretical and practical terms. this is due to the purely declarative nature of ASP that, on the one hand, calls for solver-independent methodologies and, on the other hand, does not directly apply to tracing techniques. In this paper, we propose a novel methodology, which rests within ASP itself, to sort out errors on the conceptual level. Our method makes use of tagging, where the program to be analyzed is rewritten using dedicated control atoms. this provides a flexible way to specify different types of debugging requests and a first step towards a dedicated (meta level) debugging language.
the present, in this paper, a framework supporting a formal verification of UML diagrams using the Maude language. the approach considers both static and dynamic features of object-oriented systems. We focus, in parti...
详细信息
ISBN:
(纸本)9780769530352
the present, in this paper, a framework supporting a formal verification of UML diagrams using the Maude language. the approach considers both static and dynamic features of object-oriented systems. We focus, in particular, on UML class, state and communication diagrams. the formal and object-oriented language Maude, based on rewriting logic, supports formal specification and programming of concurrent systems, as well as model checking. the major motivations of this work are: (1) bind together the UML notation and the Maude language (2) preserve the coherence in object-oriented systems description, (3) use model checking techniques to support formally their verification process. the generated Maude specifications, from the considered UML diagrams, are validated by simulation and model checking. the approach is illustrated using a concrete case study.
We construct a sound, complete, and terminating tableau system for the interval temporal logic D interpreted in interval structures over dense linear orderings endowed with strict subinterval relation (where both endp...
详细信息
ISBN:
(纸本)9783540730989
We construct a sound, complete, and terminating tableau system for the interval temporal logic D interpreted in interval structures over dense linear orderings endowed with strict subinterval relation (where both endpoints of the sub-interval are strictly inside the interval). In order to prove the soundness and completeness of our tableau construction, we introduce a kind of finite pseudo-models for our logic, called D(sic)-structures, and show that every formula satisfiable in D(sic): is satisfiable in such pseudo-models, thereby proving small-model property and decidability in PSPACE of D(sic) a result established earlier by Shapirovsky and Shehtman by means of filtration. We also show how to extend our results to the interval logic D(sic) interpreted over dense interval structures with proper (irreflexive) subinterval relation, which differs substantially from DE and is generally more difficult to analyze. Up to our knowledge, no complete deductive systems and decidability results for D(sic) have been proposed in the literature so far.
this paper presents an implementation of (a simplified version of) the cognitive agent programming language 3APL in the Maude term rewriting language. Maude is based on the mathematical theory of rewriting logic. the ...
详细信息
ISBN:
(纸本)9783540696186
this paper presents an implementation of (a simplified version of) the cognitive agent programming language 3APL in the Maude term rewriting language. Maude is based on the mathematical theory of rewriting logic. the language has been shown to be suitable both as a logical framework in which many other logics can be represented, and as a semantic framework, through which programming languages with an operational semantics can be implemented in a rigorous way. We explore the usage of Maude in the context of agent programming languages, and argue that, since agent programming languages such as 3APL have both a logical and a semantic component, Maude is very well suited for prototyping such languages. Further, we show that, since Maude is reflective, 3APL's meta-level reasoning cycle or deliberation cycle can be implemented very naturally in Maude. Moreover, although we have implemented a simplified version of 3APL, we argue that Maude is very well suited for implementing various extensions of this implemented version. An important advantage of Maude, besides the fact that it is well suited for prototyping agent programming languages, is that it can be used for verification as it comes with an LTL model checker. Although this paper does not focus on model checking 3APL, the fact that Maude provides these verification facilities is an important motivation for our effort of implementing 3APL in Maude.
暂无评论