首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 31 毫秒
1.
This paper considers the efficient evaluation of recursive queries expressed using Horn clauses. We define sideways information passing formally and show how a query evaluation algorithm may be defined in terms of sideways information passing and control. We then consider a class of information-passing strategies that suffices to describe most query evaluation algorithms in the database literature, and show that these strategies may always be implemented by rewriting a given program and evaluating the rewritten program bottom-up. We describe in detail several algorithms for rewriting a program. These algorithms generalize the counting and magic-sets algorithms to work with arbitrary programs. Safety and optimality of the algorithms are also considered.  相似文献   

2.
Symbolic evaluation is a technique used for many purposes: program analysis, program verification, program transformation. The paper focusses on a novel approach which allows one to symbolically evaluate programs with respect to predicates denoting subsets of a user-defined data domain. The data domain is assumed to be recursively defined and the predicates can be defined by structural induction on the data. An application of the technique to the textual reduction of recursive programs is sketched.  相似文献   

3.
We show that the decision problem for the class C0 of all closed universal Horn formulae in prenex conjunctive normal form of extended Skolem arithmetic without equality (i.e. first order formulae built up from the multiplication sign, constants for the natural numbers and free occuring predicate symbols) is exponentially time bounded equivalent to the reachability problem for Petri nets if restricted to the class of formulae with (a) only monadic predicate symbols, with (b) only binary disjunctions in the quantifier free matrix and (c) without terms containing a variable more than once. We show that leaving out one of the restrictions (a) to (c) yields classes of formulae whose decision problem can assume any prescribed recursively enumerable complexity in terms of many-one degrees of unsolvability.  相似文献   

4.
《Graphical Models》2005,67(4):347-369
This paper presents DigitalSculpture, an interactive sculpting framework founded upon iso-surfaces extracted from recursively subdivided, 3D irregular grids. Our unique implicit surface model arises from an interpolatory, volumetric subdivision scheme that is C1 continuous across the domains defined by arbitrary 3D irregular grids. We assign scalar coefficients and color to each control vertex and allow these quantities to participate in the volumetric subdivision of irregular grids. In the subdivision limit, a virtual sculpture is obtained by extracting the zero-level from the volumetric, scalar field defined over the irregular grid. This novel shape geometry extends concepts from solid modeling, recursive subdivision, and implicit surfaces; facilitates many techniques for interactive sculpting; permits rapid, local evaluation of iso-surfaces; and affords level-of-detail control of the sculpted surfaces.  相似文献   

5.
A formalism is presented for tracking assertions which hold universally, i.e., at the end of all the execution paths to a given program point, and assertions which hold existentially, i.e., at the end of some execution paths. In the formalism, the assertions which hold at a given execution path are uniformly defined by an entry environment which contains the assertions which hold when the execution of the program begins and an environment transformer for every program construct. The novel aspect of our formalism is that Horn clauses are used to specify the consistent environments and the meaning of program constructs. The best iterative algorithm (a notion defined by P. Cousot and R. Cousot) for tracking universal and existential assertions simultaneously is given. Conditions are presented under which the best iterative algorithm can be efficiently implemented. The formalism is applied to the pointer equality problem in Pascal. It is shown that universal pointer equalities may be used to reduce the number of superfluous existential equalities, and that existential equalities may be used to obtain more universal equalities. Recent empirical results indicate that tracking the combination of may and must equalities leads to substantial improvements in the result of the analysis. For programs without recursively defined records, the best iterative algorithm can be effectively implemented. These results apply to multiple levels of pointers and can be extended to handle possibly recursive procedures. However, for programs with recursively defined data types further approximations are necessary, e.g., by using a finite graph to model all the possible pointer equalities. For simplicity, this paper does not present an analysis algorithm for this case. Received: 2 September 1991 / 25 June 1997  相似文献   

6.
The problem of Horn Minimization (HM) can be stated as follows: given a Horn CNF representing a Boolean function f, find a shortest possible (optimally compressed) CNF representation of f, i.e., a CNF representation of f which consists of the minimum possible number of clauses. This problem is the formalization of the problem of knowledge compression for speeding up queries to propositional Horn expert systems, and it is known to be NP-hard. There are two subclasses of Horn functions for which HM is known to be solvable in polynomial time: acyclic and quasi-acyclic Horn functions. In this paper we define a new class of Horn functions properly containing both of the known classes and design a polynomial time HM algorithm for this new class.  相似文献   

7.
In this paper we use the fixpoint approach in formalizing the equivalence of recursively defined functions within the framework of predicate calculus. The results suggest some general mathematical techniques useful in proving equivalence of recursive programs.  相似文献   

8.
We consider the problem of dualizing a Boolean function f given by CNF, i.e., computing a CNF for its dual fd. While this problem is not solvable in quasi-polynomial total time in general (unless SAT is solvable in quasi-polynomial time), it is so in case the input belongs to special classes, e.g., the class of bidual Horn CNF ? [Discrete Appl. Math. 96-97 (1999) 55-88] (i.e., both ? and its dual ?d represent Horn functions). In this paper, we show that a disguised bidual Horn CNF ? (i.e., ? becomes a bidual Horn CNF after renaming of variables) can be recognized in polynomial time, and its dualization can be done in quasi-polynomial total time. We also establish a similar result for dualization of prime CNFs.  相似文献   

9.
模糊Horn子句规则可以用自然语言来表达人类知识。但是,发现模糊Horn子句规则及其蕴含度是比较困难的。该文从逻辑的观点出发,定义模糊Horn子句规则、支持度、蕴含度及其相关概念,分析模糊Horn子句规则发现的步骤,并给出发现算法的形式化描述。该算法结合了模糊Horn子句逻辑概念和Apriori发现算法,从给定的数量型数据库中发现模糊Horn子句规则。  相似文献   

10.
The formal semantics of a given Horn sentence is usually defined as a set of ground atoms, which is really the minimal Herbrand interpretation of the Horn sentence, by both model-theoretic and fixpoint approaches. In the present paper, we propose another denotational semantics of a Horn sentence, denoting the set of substitutions with which atoms are derivable by unit deduction from the Horn sentence to get a direct correspondence between the semantics of the Horn sentence and the answer set concerned with its computation, and give denotational semantics even when the Horn sentence is unsatisfiable. In accordance with the unit deductions from a Horn sentence, we define a continuous function from a direct product of powersets of a substitution set to itself, and regard the least fixpoint of the function as the semantics, which can provide the answer set for computations of the Horn sentence.  相似文献   

11.
This paper presents a generalization of Shapiro style algorithmic debugging for generalized Horn clause intuitionistic logic. This logic offers hypothetical reasoning and negation is defined not by failure but by inconsistency. We extend Shapiro's notion of intended interpretation, symptoms and errors and give formal results paralleling those known for definite clauses. We also show how a corresponding diagnosis module for RISC- a logic programming system for generalized Horn clause intuitionistic logic-can be defined by meta interpretation. In contrast to Shapiro's PROLOG modules ours work independently of the specific computation rule that in RISC may be specified by the user.  相似文献   

12.
Four statements equivalent to well-foundedness (well-founded induction, existence of recursively defined functions, uniqueness of recursively defined functions, and absence of descending -chains) have been proved in Mizar and the proofs mechanically checked for correctness. It seems not to be widely known that the existence (without the uniqueness assumption) of recursively defined functions implies well-foundedness. In the proof we used regular cardinals, a fairly advanced notion of set theory. The theory of cardinals in Mizar was developed earlier by G. Bancerek. With the current state of the Mizar system, the proofs turned out to be an exercise with only minor additions at the fundamental level. We would like to stress the importance of a systematic development of a mechanized data base for mathematics in the spirit of the QED Project. 12pt ENOD – Experience, Not Only DoctrineG. Kreisel  相似文献   

13.
We give a new algorithm for computing a prepositional Horn CNF formula given the set of its models. Its running time is O(|R|n(|R|+n)), where |R| is the number of models and n that of variables, and the computed CNF contains at most |R|n clauses. This algorithm also uses the well-known closure property of Horn relations in a new manner.  相似文献   

14.
A Fuzzy Proof Theory   总被引:1,自引:0,他引:1       下载免费PDF全文
Based on the first order peicate logic,in this paper,we present a new approach to generalizing the syntax of ordinary Horn clause rules to establish a fuzzy proof theory,First of all,each Horn clause rule is associated with a numerical implication strength f.Therefore we obtain f-Horn clause rules.Secondly,Herbrand interpretations can be generalized to fuzzy subsets of the Herbrand base in the sense of Zadch.As a result the proof theory for Horn clause rules can be developed in much the same way for f-Horm clause rules.  相似文献   

15.
Shading logic: a heuristic approach to recover shape from shading   总被引:4,自引:0,他引:4  
A heuristic-based algorithm known as the shading logic algorithm is proposed for recovering shape from shading. The heuristics are derived on the basis of a geometrical interpretation of the M.J. Brooks and B.K.P. Horn (1985) algorithm. An experimental evaluation was performed using synthesized objects, in particular, superquadrics. The advantage of using the superquadrics is that the shape of the objects can be varied incrementally and systematically. Despite the fact that the shading logic algorithm is heuristic based, experimental results show that the proposed algorithm has a better performance than the Brooks and Horn algorithm. In addition, the proposed approach does not seem to suffer the stability problem common to most variational-based methods  相似文献   

16.
Feedforward neural network architectures work well for numerical data of fixed size, such as images. For variable size, structured data, such as sequences, d dimensional grids, trees, and other graphs, recursive architectures must be used. We distinguish two general approaches for the design of recursive architectures in deep learning, the inner and the outer approach. The inner approach uses neural networks recursively inside the data graphs, essentially to “crawl” the edges of the graphs in order to compute the final output. It requires acyclic orientations of the underlying graphs. The outer approach uses neural networks recursively outside the data graphs and regardless of their orientation. These neural networks operate orthogonally to the data graph and progressively “fold” or aggregate the input structure to produce the final output. The distinction is illustrated using several examples from the fields of natural language processing, chemoinformatics, and bioinformatics, and applied to the problem of learning from variable-size sets.  相似文献   

17.
In this paper, we define double Horn functions, which are the Boolean functionsfsuch that bothfand its complement (i.e., negation)fare Horn, and investigate their semantical and computational properties. Double Horn functions embody a balanced treatment of positive and negative information in the course of the extension problem of partially defined Boolean functions (pdBfs), where a pdBf is a pair (T, F) of disjoint setsT, F⊆{0, 1}nof true and false vectors, respectively, and an extension of (T, F) is a Boolean functionfthat is compatible withTandF. We derive syntactic and semantic characterizations of double Horn functions, and determine the number of such functions. The characterizations are then exploited to give polynomial time algorithms (i) that recognize double Horn functions from Horn DNFs (disjunctive normal forms), and (ii) that compute the prime DNF from an arbitrary formula, as well as its complement and its dual. Furthermore, we consider the problem of determining a double Horn extension of a given pdBf. We describe a polynomial time algorithm for this problem and moreover an algorithm that enumerates all double Horn extensions of a pdBf with polynomial delay. However, finding a shortest double Horn extension (in terms of the size of a formula?representing it) is shown to be intractable.  相似文献   

18.
In this paper we propose a new minimum total communication distance (TCD) algorithm and an optimal TCD algorithm for broadcast in a 3-dimensional mesh (3-D mesh). The former generates a minimum TCD from a given source node, and the latter guarantees a minimum TCD among all the possible source nodes. These algorithms are based on a divide-and-conquer approach where a 3-D mesh is partitioned into eight submeshes of equal size. The source node sends the broadcast message to a special node called an eye in each submesh. The above procedure is then recursively applied in each submesh. The proposed approach can be generalized to a d-dimensional mesh or torus. In addition, the proposed approach can potentially be used to solve optimization problems in other collective communication operations.  相似文献   

19.
A virtual relation (or view) can be defined with a recursive Horn clause that is a function of one or more base relations. In general, the number of times such a Horn clause must be applied in order to retrieve all the tuples in the virtual relation depends on the contents of the base relations of the definition. However, there exist Horn clauses for which there is an upper bound on the number of applications necessary to form the virtual relation, independent of the contents of the base relations. Considering a restricted class of recursive Horn clauses, we give necessary and sufficient conditions for members of the class to have this bound.  相似文献   

20.
Since Selman and Kautz's seminal work on the use of Horn approximation to speed up the querying of knowledge bases, there has been great interest in Boolean approximation for AI applications. There are several Boolean classes with desirable computational properties similar to those of the Horn class. The class of affine Boolean functions, for example, has been proposed as an interesting alternative to Horn for knowledge compilation. To investigate the trade-offs between precision and efficiency in knowledge compilation, we compare, analytically and empirically, four well-known Boolean classes, and their combinations, for ability to preserve information. We note that traditional evaluation which explores unit-clause consequences of random hard 3-CNF formulas does not tell the full story, and we complement that evaluation with experiments based on a variety of assumptions about queries and the underlying knowledge base.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号