We show that a minimal dependent type theory based on Sigma-types and equality is degenerated in presence of computational classical logic. By computational classical logic is meant a classical logic derived from a co...
详细信息
ISBN:
(数字)9783540320142
ISBN:
(纸本)3540255931
We show that a minimal dependent type theory based on Sigma-types and equality is degenerated in presence of computational classical logic. By computational classical logic is meant a classical logic derived from a control operator equipped with reduction rules similar to the ones of Felleisen's C or Parigot's mu operators. As a consequence, formalisms such as Martin-Lof's type theory or the (Set-predicative variant of the) Calculus of Inductive Constructions are inconsistent in presence of computational classical logic. Besides, an analysis of the role of the eta-rule for control operators through a set-theoretic model of computational classical logic is given.
In this work we describe a system for determining strong equivalence of disjunctive non-ground datalog programs under the stable model semantics. The problem is tackled by reducing it to the unsatisfiability problem o...
详细信息
ISBN:
(纸本)3540285385
In this work we describe a system for determining strong equivalence of disjunctive non-ground datalog programs under the stable model semantics. The problem is tackled by reducing it to the unsatisfiability problem of first-order formulas in the Bernays-Schonfinkel fragment. We then employ a tableaux-based theorem prover, which (unlike most other currently available provers) is guaranteed to terminate for these formulas. To the best of our knowledge, this is the first strong equivalence tester for disjunctive non-ground datalog.
The online recommendations are a popular presence in the Web sites world due to their potential to increase the customers' satisfaction. The ability to represent epistemic information about the clients' belief...
详细信息
ISBN:
(纸本)076952415X
The online recommendations are a popular presence in the Web sites world due to their potential to increase the customers' satisfaction. The ability to represent epistemic information about the clients' beliefs is important to understand their needs. This paper presents a recommender system based on reinforcement learning. The system represents concepts presented on a Web site by epistemic logical programs and uses a similarity measure between programs in order to facilitate generalization. A prototype of this system and experiments are presented.
This paper describes a system called SELP for studying strong equivalence in answer set logic programming. The basic function of the system is to check if two given ground disjunctive logic programs are equivalent, an...
详细信息
ISBN:
(纸本)3540285385
This paper describes a system called SELP for studying strong equivalence in answer set logic programming. The basic function of the system is to check if two given ground disjunctive logic programs are equivalent, and if not, return a counter-example. We have used the system to discover some interesting theorems about strong equivalence [Lin and Chen, 2005]. Here we briefly describe how the system can be used to find out whether a given set of rules is strongly equivalent to another, perhaps simpler set of rules.
In this work, we devise an analysis that searches for semantically equivalent code fragments within a given logic program. The presence of duplicated code (or functionality) is a primary indication that the design of ...
详细信息
ISBN:
(纸本)3540266550
In this work, we devise an analysis that searches for semantically equivalent code fragments within a given logic program. The presence of duplicated code (or functionality) is a primary indication that the design of the program can be improved by performing a so-called refactoring transformation. Within the framework of our analysis, we formally characterize three situations of duplicated functionality and their associated refactorings: the extraction of a duplicated goal into a new predicate, the removal of equivalent predicates and the generalization of two predicates into a higher-order predicate. The resulting analysis detects in a completely automatic way what program fragments are suitable candidates for the considered refactoring transformations.
We study and further develop two language-based techniques for analyzing security protocols. One is based on a typed process calculus;the other, on untyped logic programs. Both focus on secrecy properties. We contribu...
详细信息
ISBN:
(纸本)9781581134506
We study and further develop two language-based techniques for analyzing security protocols. One is based on a typed process calculus;the other, on untyped logic programs. Both focus on secrecy properties. We contribute to these two techniques, in particular by extending the former with a flexible, generic treatment of many cryptographic operations. We also establish an equivalence between the two techniques.
Labeled unranked trees are used as a model of XML documents, and logical languages for them have been studied actively over the past several years. Such logics have different purposes: some are better suited for extra...
详细信息
ISBN:
(纸本)3540275800
Labeled unranked trees are used as a model of XML documents, and logical languages for them have been studied actively over the past several years. Such logics have different purposes: some are better suited for extracting data, some for expressing navigational properties, and some make it easy to relate complex properties of trees to the existence of tree automata for those properties. Furthermore, logics differ significantly in their model-checking properties, their automata models, and their behavior on ordered and unordered trees. In this paper we present a survey of logics for unranked trees.
The hybrid logic H(@) is obtained by adding nominals and the satisfaction operator @ to the basic modal logic. The resulting logic gains expressive power without increasing the complexity of the satisfiability problem...
详细信息
ISBN:
(纸本)3540252363
The hybrid logic H(@) is obtained by adding nominals and the satisfaction operator @ to the basic modal logic. The resulting logic gains expressive power without increasing the complexity of the satisfiability problem, which remains within PSpace. A resolution calculus for H(@) was introduced in [5], but it did not provide strategies for ordered resolution and selection functions. Additionally, the problem of termination was left open. In this paper we address both issues. We first define proper notions of admissible orderings and selection functions and prove the refutational completeness of the obtained ordered resolution calculus using a standard "candidate model" construction [10]. Next, we refine some of the nominal-handling rules and show that the resulting calculus is sound, complete and can only generate a finite number of clauses, establishing termination. Finally, the theoretical results were tested empirically by implementing the new strategies into HyLoRes [6,18], an experimental prototype for the original calculus described in [5]. Both versions of the prover were compared and we discuss some preliminary results.
Recently, linear logic has been used to specify sequent calculus proof systems in such a way that the proof search in linear logic can yield proof search in the specified logic. Furthermore, the meta-theory of linear ...
详细信息
ISBN:
(纸本)354030553X
Recently, linear logic has been used to specify sequent calculus proof systems in such a way that the proof search in linear logic can yield proof search in the specified logic. Furthermore, the meta-theory of linear logic can be used to draw conclusions about the specified sequent calculus. For example, derivability of one proof system from another can be decided by a simple procedure that is implemented via bounded logic programming-style search. Also, simple and decidable conditions on the linear logic presentation of inference rules, called homogeneous and coherence, can be used to infer that the initial rules can be restricted to atoms and that cuts can be eliminated. In the present paper we introduce Llinda, a logical framework based on linear logic augmented with inference rules for definition (fixed points) and induction. In this way, the above properties can be proved entirely inside the framework. To further illustrate the power of Llinda, we extend the definition of coherence and provide a new, semi-automated proof of cut-elimination for Girard's logic of Unicity (LU).
Aggregates in answer set programming (ASP) have recently been studied quite intensively. The main focus of previous work has been on defining suitable semantics for programs with arbitrary, potentially recursive aggre...
详细信息
ISBN:
(纸本)3540285385
Aggregates in answer set programming (ASP) have recently been studied quite intensively. The main focus of previous work has been on defining suitable semantics for programs with arbitrary, potentially recursive aggregates. By now, these efforts appear to have converged. On another line of research, the relation between unfounded sets and (aggregate-free) answer sets has lately been rediscovered. It turned out that most of the currently available answer set solvers rely on this or closely related results (e.g., loop formulas). In this paper, we unite these lines and give a new definition of unfounded sets for disjunctive logic programs with arbitrary, possibly recursive aggregates. While being syntactically somewhat different, we can show that this definition properly generalizes all main notions of unfounded sets that have previously been defined for fragments of the language. We demonstrate that, as for restricted languages, answer sets can be crisply characterized by unfounded sets: They are precisely the unfounded-free models. This result can be seen as a confirmation of the robustness of the definition of answer sets for arbitrary aggregates. We also provide a comprehensive complexity analysis for unfounded sets, and study its impact on answer set computation.
暂无评论