Introducing universal quantifiers and some forms of implications into goals provides for scoping constructs in logic programming. We address the new implementation problems raised by the addition of these logical symb...
详细信息
ISBN:
(纸本)0262560585
Introducing universal quantifiers and some forms of implications into goals provides for scoping constructs in logic programming. We address the new implementation problems raised by the addition of these logical symbols. The presence of mixed sequences universal and existential quantifiers in goals requires unification to respect this ordering, a problem we solve by using a scheme for tagging constants and variables. A few changes to existing WAM (Warren Abstract Machine) instructions suffice to implement this scheme. Implication in goals cause new program clauses to be introduced, and the implementation must therefore accommodate a dynamically changing set of program clauses. A naive asserting and retracting of program clauses is an unsatisfactory solution to this problem in view of backtracking. Further, when an implication goal is surrounded by existential quantifiers, the introduced program clauses may have to be parameterized by the bindings for these existential variables, thus requiring program clauses to be treated as program closures. We use a hash-table for efficient access to the clauses and a new kind of record, called an implication point record, to manage the interaction between backtracking and dynamic nesting of implication goals. New instructions for the WAM are proposed for compiling quantifiers and implications in goals.
In this work, we introduce a new method for searching stable models of logical programs. This method is based on a relatively new semantics that has not been exploited yet. This semantics captures and extends that one...
详细信息
ISBN:
(纸本)9781538674499
In this work, we introduce a new method for searching stable models of logical programs. This method is based on a relatively new semantics that has not been exploited yet. This semantics captures and extends that one of the stable models (Gelfond et al., 1988) and offers a new alternative to implement ASP solvers. The proposed method performs a DPLL enumerative process that is adapted to Answer Set programming (ASP) framework according to the used semantics. This method has the advantage to use a Horn clause representation having the same size as the input logic program has constant spatial complexity. It avoids the workload induced by the loop management from which suffer most of the ASP solvers based on the Clark completion. Moreover, the enumeration is done on a restricted set of literals called the strong back-door (STB) of the considered logic program. This reduces the algorithm time complexity which is in theory a function of the size of the STB set. We also introduced new inference rules that the method uses to prune its search tree and hence reduces its size in practice. We implemented the proposed method and applied it to enumerate the stable models of some combinatorial problems. The method is compared to other known systems and the obtained results show that our approach is a good alternative for designing ASP solvers.
Perfect relaxation is a very efficient solution technique for any structured discrete constraint satisfaction problem (CSP), i.e. a CSP which has been incrementally generated in a sequence of steps by adding, at each ...
详细信息
ISBN:
(纸本)0262560585
Perfect relaxation is a very efficient solution technique for any structured discrete constraint satisfaction problem (CSP), i.e. a CSP which has been incrementally generated in a sequence of steps by adding, at each step, some bounded quantity of its constraints. In this paper we consider the constraint logic programming framework, which is a very natural constraint programming paradigm, and we show how it can take advantage of the perfect relaxation technique during its computations. We do that by first showing that each computation step involves the solution of a structured CSP, and then by describing how to use the previous steps of the computation as a guidance for perfect relaxation. Thus each computation becomes a sequence of linear steps, since each step applies a perfect relaxation algorithm, which is linear in the size of the current constraint problem. This results in a rather efficient way to execute constraint logic programs with finite domains. In fact, each step is linear instead of possibly exponential, and failures are discovered much earlier due to the very nature of relaxation.
We introduce a generalized logic programming paradigm where programs, consisting of facts and rules with the usual syntax, can be enriched by co-facts, which syntactically resemble facts but have a special meaning. As...
详细信息
We introduce a generalized logic programming paradigm where programs, consisting of facts and rules with the usual syntax, can be enriched by co-facts, which syntactically resemble facts but have a special meaning. As in coinductive logic programming, interpretations are subsets of the complete Herbrand basis, including infinite terms. However, the intended meaning (declarative semantics) of a program is a fixed point which is not necessarily the least, nor the greatest one, but is determined by co-facts. In this way, it is possible to express predicates on non well-founded structures, such as infinite lists and graphs, for which the coinductive interpretation would be not precise enough. Moreover, this paradigm nicely subsumes standard (inductive) and coinductive logic programming, since both can be expressed by a particular choice of co-facts, hence inductive and coinductive predicates can coexist in the same program. We illustrate the paradigm by examples, and provide declarative and operational semantics, proving the correctness of the latter. Finally, we describe a prototype meta-interpreter.
A major technique to address state explosion problem in model checking is abstraction. Predicate abstraction has been applied successfully to large software and now to hardware descriptions, such as Verilog. This pape...
详细信息
ISBN:
(纸本)3540298967
A major technique to address state explosion problem in model checking is abstraction. Predicate abstraction has been applied successfully to large software and now to hardware descriptions, such as Verilog. This paper evaluates the state-of-the-art AI techniques-constraint logic programming (CLP)-to improve the performance of predication abstraction of hardware designs, and compared it with the SAT-based predicate abstraction techniques. With CLP based techniques, we can model various constraints, such as bit, bit-vector and integer, in a uniform framework;we can also model the word-level constraints without flatting them into bit-level constraints as SAT-based method does. With these advantages, the computation of abstraction system can be more efficient than SAT-based techniques. We have implemented this method, and the experimental results have shown the promising improvements on the performance of predicate abstraction of hardware designs.
The study of fixpoints has long been at the heart of logic programming. However, whereas least fixpoint semantics works well for SLD-refutations (i.e. is sound and complete), there is no satisfactory (i.e. complete) f...
详细信息
The study of fixpoints has long been at the heart of logic programming. However, whereas least fixpoint semantics works well for SLD-refutations (i.e. is sound and complete), there is no satisfactory (i.e. complete) fixpoint semantics for infinite derivations. In this paper, we focus on this problem. Standard approaches in this area consist in concentrating on infinite derivations that can be seen as computing, in the limit, some infinite object. This is usually done by extending the domain of computation with infinite elements and then defining the meaning of programs in terms of greatest fixpoints. The main drawback of these approaches is that the semantics defined is not complete. Hence, since defining a greatest fixpoint semantics for logic programs amounts to consider a program as a set of co-inductive definitions, we focus on this identification at a deeper level by considering infinite derivations as proof-terms in a co-inductive set. This reading leads into considering derivations as proofs rather than computations and allows one to show that for the subclass of infinite derivations over the domain of finite terms, a complete greatest fixpoint semantics can be obtained. Our main result is that the greatest fixpoint of the one-step-inference operator for the C-semantics corresponds to atoms that have a non-failing fair derivation with the additional property that complete information over a variable is obtained after finitely many steps.
ILP systems have been largely applied to datamining classification tasks with a considerable success. The use of ILP systems in regression tasks has been far less successful. Current systems have very limited numerica...
详细信息
ISBN:
(纸本)0769521428
ILP systems have been largely applied to datamining classification tasks with a considerable success. The use of ILP systems in regression tasks has been far less successful. Current systems have very limited numerical reasoning capabilities, which limits the application of ILP to discovery of functional relationships of numeric nature. This paper proposes improvements in numerical reasoning capabilities of ILP systems for dealing with regression tasks. It proposes the use of statistical-based techniques like Model Validation and Model Selection to improve noise handling and it introduces a new search stopping criterium based on the PAC method to evaluate learning performance. We have found these extensions essential to improve on results over machine learning and statistical-based algorithms used in the empirical evaluation study.
The Information and Communication Technology (ICT) have been successfully used to transform either partial/total face to face or distance learning education [1]. Educational software systems aid the teaching/learning ...
详细信息
ISBN:
(纸本)9781457703485
The Information and Communication Technology (ICT) have been successfully used to transform either partial/total face to face or distance learning education [1]. Educational software systems aid the teaching/learning process, promoting the development of a lot of Virtual Learning Environments (VLEs), improving the assimilation of the content presented in the class. Using mechanisms such as Hardware as a Service (HaaS) and Software as a Service (SaaS), it is possible to envision a new concept: Education as a Service - EdaaS.
We present a technique to embed a functional logic language in Haskell using a GHC plugin. Our approach is based on a monadic lifting that models the functional logic semantics explicitly. Using a GHC plugin, we get m...
详细信息
ISBN:
(纸本)9783031248405;9783031248412
We present a technique to embed a functional logic language in Haskell using a GHC plugin. Our approach is based on a monadic lifting that models the functional logic semantics explicitly. Using a GHC plugin, we get many language extensions that GHC provides for free in the embedded language. As a result, we obtain a seamless embedding of a functional logic language, without having to implement a full compiler. We briefly show that our approach can be used to embed other domainspecific languages as well. Furthermore, we can use such a plugin to build a full blown compiler for our language.
The issue of value invention in logic programming embraces many scenarios, such as logic programming with function symbols, object oriented logic languages, inter-operability with external sources of knowledge, set un...
详细信息
ISBN:
(纸本)354039625X
The issue of value invention in logic programming embraces many scenarios, such as logic programming with function symbols, object oriented logic languages, inter-operability with external sources of knowledge, set unification. This paper introduces a framework embedding value invention in a general context. The class of programs having a suitable (but, in general, not decidable) 'finite grounding property' is identified, and the class of 'value invention restricted' programs is introduced. Value invention restricted programs have the finite grounding property and can be decided in polynomial time. They are, in a sense, the broadest polynomially decidable class having this property, whenever no assumption can be made about the nature of invented values (while this latter is the case in the specific literature about logic programming with function symbols). Relationships with existing formalisms are eventually discussed;in particular, value invention restricted programs subsume omega-restricted programs and are incomparable with finitary programs.
暂无评论