Totally correct logic program transformations via well-founded annotations

We address the problem of proving the total correctness of transformations of definite logic programs. We consider a general transformation rule, called clause replacement, which consists in transforming a program P into a new program Q by replacing a set Γ ₁ of clauses occurring in P by a new set Γ ₂ of clauses, provided that Γ ₁ and Γ ₂ are equivalent in the least Herbrand model M(P) of the program P. We propose a general method for proving that transformations based on clause replacement are totally correct, that is, M(P)=M(Q). Our method consists in showing that the transformation of P into Q can be performed by: (i) adding extra arguments to predicates, thereby deriving from the given program P an annotated program $\overline{P}$ , (ii) applying a variant of the clause replacement rule and transforming the annotated program $\overline{P}$ into a terminating annotated program $\overline{Q}$ , and (iii) erasing the annotations from $\overline{Q}$ , thereby getting Q. Our method does not require that either P or Q are terminating and it is parametric with respect to the annotations. By providing different annotations we can easily prove the total correctness of program transformations based on various versions of the popular unfolding, folding, and goal replacement rules, which can all be viewed as particular cases of our clause replacement rule.     

Łukasiewicz logic and Riesz spaces

We initiate a deep study of Riesz MV-algebras which are MV-algebras endowed with a scalar multiplication with scalars from \([0,1]\) . Extending Mundici’s equivalence between MV-algebras and \(\ell \) -groups, we prove that Riesz MV-algebras are categorically equivalent to unit intervals in Riesz spaces with strong unit. Moreover, the subclass of norm-complete Riesz MV-algebras is equivalent to the class of commutative unital C \(^*\) -algebras. The propositional calculus \({\mathbb R}{\mathcal L}\) that has Riesz MV-algebras as models is a conservative extension of ?ukasiewicz \(\infty \) -valued propositional calculus and is complete with respect to evaluations in the standard model \([0,1]\) . We prove a normal form theorem for this logic, extending McNaughton theorem for ? ukasiewicz logic. We define the notions of quasi-linear combination and quasi-linear span for formulas in \({\mathbb R}{\mathcal L},\) and relate them with the analogue of de Finetti’s coherence criterion for \({\mathbb R}{\mathcal L}\) .     

Revising Z: Part I – logic and semantics

This is the first of two related papers. We introduce a simple specification logic Z _C comprising a logic and a semantics (in ZF set theory) within which the logic is sound. We then provide an interpretation for (a rational reconstruction of) the specification language Z within Z _C . As a result we obtain a sound logic for Z, including a basic schema calculus. Received March 1998 / Accepted in revised form April 1999     

Geometry optimization within a modified extended Hückel formalism: Modifications to the ASED program

The ASED program by Anderson and coworkers was modified to include a full geometry optimizer. It was discovered that, even with this modification, the ASED program could not be used to perform geometry optimizations on organic molecules without further modification. These modifications included changing the Wolfsberg-Helmholz equation used in the ASED program back to the original equation found in the FORTICON8 program as well as changing the Slater orbital exponents. A general parameter set for C, H, O and N has been developed, which has been used to perform geometry optimizations on selected organic molecules. The calculated geometries compared reasonably with the experimental values and with previously published AM1 geometries.     

Boosting learning and inference in Markov logic through metaheuristics

Markov Logic (ML) combines Markov networks (MNs) and first-order logic by attaching weights to first-order formulas and using these as templates for features of MNs. State-of-the-art structure learning algorithms in ML maximize the likelihood of a database by performing a greedy search in the space of structures. This can lead to suboptimal results because of the incapability of these approaches to escape local optima. Moreover, due to the combinatorially explosive space of potential candidates these methods are computationally prohibitive. We propose a novel algorithm for structure learning in ML, based on the Iterated Local Search (ILS) metaheuristic that explores the space of structures through a biased sampling of the set of local optima. We show through real-world experiments that the algorithm improves accuracy and learning time over the state-of-the-art algorithms. On the other side MAP and conditional inference for ML are hard computational tasks. This paper presents two algorithms for these tasks based on the Iterated Robust Tabu Search (IRoTS) metaheuristic. The first algorithm performs MAP inference and we show through extensive experiments that it improves over the state-of-the-art algorithm in terms of solution quality and inference time. The second algorithm combines IRoTS steps with simulated annealing steps for conditional inference and we show through experiments that it is faster than the current state-of-the-art algorithm maintaining the same inference quality.     

Decidable subsets of open logic and an algorithm for R-calculus

Open logic is an attractive logic theory that can describe the growth and evolution of knowledge.However, related studies show that open logic is undecidable in first-order logic and thus is hard to be programmed. This paper proposes that open logic should be implemented with constraints, and provides a set of syntax constraints under which open logic is decidable. Furthermore, it is shown that the constraints are necessary and sufficient for the decidable formulas of open logic. A Domino problem-based algorithm R-CP that implements the R-calculus of the constrained open logic is presented and its reachability is proved.     

A modal contrastive logic: The logic of ‘but’

In this paper we present a modal approach to contrastive logic, the logic of contrasts as these appear in natural language conjunctions such as but. We use a simple modal logic, which is an extension of the well-knownS5 logic, and base the contrastive operators proposed by Francez in [2] on the basic modalities that appear in this logic. We thus obtain a logic for contrastive operators that is more in accord with the tradition of intensional logic, and that, moreover — we argue — has some more natural properties. Particularly, attention is paid to nesting contrastive operators. We show that nestings of but give quite natural results, and indicate how nestings of other contrastive operators can be done adequately. Finally, we discuss the example of the Hangman's Paradox and some similarities (and differences) with default reasoning. But but us no buts, as they say.Also partially supported by Nijmegen University, Toernooiveld, 6525 ED Nijmegen, The Netherlands.     

Why nonmonotonic logic?

The motivation for nonmonotonic logic is to produce a machine representation for default reasoning, broadly construed. In this paper we argue that all nonmonotonic logics have (by definition) inference rules that fail to preserve truth, and this fact leads to several undesirable features. In response to these problems, but recognizing the importance of the original motivation for nonmonotonic logic, we propose an alternative to nonmonotonic logic, which achieves nonmonotonicity of reasoning without abandoning in any way truth preserving inferences. This approach is based on a possible worlds framework, which we illustrate with a small Prolog program. Motivating this approach is an important distinction, which we believe the advocates of nonmonotonic logic to be ignoring: that between inferencing and making decisions, or equivalently that between inferencing and theory construction.     

Recursive algorithm and accurate computation of dyadic Green's functions for stratified uniaxial anisotropic media

A recursive algorithm is adopted for the computation of dyadic Green's functions in three-dimensional stratified uniaxial anisotropic media with arbitrary number of layers. Three linear equation groups for computing the coefficients of the Som- merfeld integrals are obtained according to the continuity condition of electric and magnetic fields across the interface between different layers, which are in corre- spondence with the TM wave produced by a vertical unit electric dipole and the TE or TM wave produced by a horizontal unit electric dipole, respectively. All the linear equation groups can be solved via the recursive algorithm. The dyadic Green's functions with source point and field point being in any layer can be conveniently obtained by merely changing the position of the elements within the source term of the linear equation groups. The problem of singularities occurring in the Sommer- feld integrals is efficiently solved by deforming the integration path in the complex plane. The expression of the dyadic Green's functions provided by this paper is terse in form and is easy to be programmed, and it does not overflow. Theoretical analysis and numerical examples show the accuracy and effectivity of the algo-rithm.     

<Emphasis Type="Italic">FC</Emphasis>-normal and extended stratified logic program

This paper investigates the consistency property ofFC-normal logic program and presents an equivalent deciding condition whether a logic programP is anFC-normal program. The deciding condition describes the characterizations ofFC-normal program. By the Petri-net presentation of a logic program, the characterizations of stratification ofFC-normal program are investigated. The stratification ofFC-normal program motivates us to introduce a new kind of stratification, extended stratification, over logic program. It is shown that an extended (locally) stratified logic program is anFC-normal program. Thus, an extended (locally) stratified logic program has at least one stable model. Finally, we have presented algorithms about computation of consistency property and a few equivalent deciding methods of the finiteFC-normal program.     

The Least Fixpoint Transformation for Disjunctive Logic Programs

The paradigm of disjunctive logic programming(DLP)enhances greatly the expressive power of normal logic programming(NLP)and many(declarative)semantics have been defined for DLP to cope with various problems of knowledge representation in artificial intelligence.However,the expressive ability of the semantics and the soundness of program transformations for DLP have been rarely explored.This paper defines an immediate consequence operatro T^GP for each disjunctive program and shows that T^GP has the least and computable fixpoint Lft(P),Lft is,in fact,a program transformation for DLP,which transforms all disjunctive programs into negative programs.It is shown that Lft preserves many key semantics,including the disjunctive stable models,well-founded model,disjunctive argunent semantics DAS,three-valued models,ect.Thic means that every disjunctive program P has a unique canonical form Lft(P)with respect to these semantics.As a result,the work in this paper provides a unifying framework for studying the expressive ability of various semantics for DLP On the other hand,the computing of the above semantics for negative programs is ust a trivial task,therefore,Lft(P)is also an optimization method for DLP.Another application of Lft is to derive some interesting semantic results for DLP.     

On the Relationship Between TMS and Logic Programs

The relationship between TMS and general logic programs is an important issue in non-monotonic logic programming.In this paper,we prove that,after we translate the TMS theory into a general logic program,the TMS‘s well-founded assignment (or extension) is equivalent to the corresponding general logic program‘s stable model.It means that TMS can be completely integrated into a non-monotonic logic programming environment.     

程序断言的半自动生成及证明逻辑

如何生成程序断言对于软件验证十分重要。传统方法要求既要对程序结构有深入地把握又要做繁复的Hoare三元式推演工作。为了摆脱这些琐碎事宜,将致力于探讨一种半自动的断言生成方法。为便于理解,讨论主要以XYZ/VERI系统为论述背景。XYZ/VERI 系统是一面向时序逻辑程序语言如XYZ/SE 的类Hoare逻辑交互式验证系统。该工作一定意义上完善了其验证功能。     

简单单调约束逻辑程序的良基语义研究

在介绍约束逻辑程序的相关概念的基础上,研究了简单单调约束逻辑程序约束原子的正文字前缀幂集展开方法,并证明展开后的正规逻辑约束与约束逻辑程序的等价特性.分析了正规逻辑程序的交替不动点良基模型建立的原理,将简单单调约束逻辑程序等价展开为与其等价的正规逻辑程序,以求展开后的逻辑程序中的给定算子的最小不动点为切入,给出了简单单调约束逻辑程序的交替不动点的良基模型.论证了文中提出的简单单调约束逻辑程序良基模型定义的合理性,说明把约束逻辑程序转化为正规逻辑程序是可行的.     

Proving program inclusion using Hoare's logic

We explore conservative refinements of specifications. These form a quite appropriate framework for a proof theory for program inclusion based on a proof theory for program correctness.We propose two formalized proof methods for program inclusion and prove these to be sound. Both methods are incomplete but seem to cover most natural cases.     

基于不变量的程序修复进化扩展模型*

为了有效解决程序修复进化中搜索空间过大和正常功能牺牲的问题,提出了一种基于不变量约束的扩展的程序修复进化模型（extended repair evolutionary model,EREM）,利用程序不变量约束对搜索空间进行划分和约简以降低消耗,通过使用表达程序正常功能的正测试用例学习的不变量约束（称为正不变量约束）来保证程序不牺牲正常的功能,在适应度函数的设计上考虑测试用例通过数的同时也考虑了正不变量约束的保持数,对于破坏正不变量约束的个体适应度给予一定的惩罚值。最后通过实验对模型进行了验证,结果表明了     

一种用于测试数据生成的动态程序切片算法

介绍了程序切片技术的基本概念，提出了一种基于前向分析的动态程序切片算法，探讨了程序切片在软件测试数据生成中的应用，结果表明可以有效地提高基于路径的测试数据生成效率。     

Pallet operation sequencing based on network part program logic

CAPP systems play a relevant role in aiding planners during setup planning, operation sequencing and pallet configuration activities. The support and automation granted by these techniques, together with the use of non-linear process planning logic, lead to a reduction in the planning time and costs, thus making manufacturers more competitive. This paper presents an approach that integrating process and production planning leads to the definition at the shop-floor level of the optimal operation sequence to machine all of the workpieces on a pallet using a four-axis machine tool. Part programs of non-production movements for each possible sequence of two operations are automatically generated at the shop-floor level and are simulated to obtain the non-production time. The complete sequence of operations is then defined on the basis of the minimisation of the estimated non-production time. This minimisation is performed using a mathematical model that defines a good sequence of operations. Four algorithms are adopted to analyse the proposed solution and to reduce the gap from optimality. The approach is tested on some cases taken from literature and on a real case. The real case was provided by a company that produces mechanical components. The obtained results underline a reduction on production and planning time, and consequently an increment in the company profit.