Dualities between alternative semantics for logic programming and nonmonotonic reasoning

The Gelfond-Lifschitz operator associated with a logic program (and likewise the operator associated with default theories by Reiter) exhibits oscillating behavior. In the case of logic programs, there is always at least one finite, nonempty collection of Herbrand interpretations around which the Gelfond-Lifschitz operator bounces around. The same phenomenon occurs with default logic when Reiter's operator is considered. Based on this, a stable class semantics and extension class semantics has been proposed. The main advantage of this semantics was that it was defined for all logic programs (and default theories), and that this definition was modelled using the standard operators existing in the literature such as Reiter's operator. In this paper our primary aim is to prove that there is a very interestingduality between stable class theory and the well-founded semantics for logic programming. In the stable class semantics, classes that were minimal with respect to Smyth's power-domain ordering were selected. We show that the well-founded semantics precisely corresponds to a class that is minimal w.r.t. Hoare's power domain ordering: the well-known dual of Smyth's ordering. Besides this elegant duality, this immediately suggests how to define a well-founded semantics for default logic in such a way that the dualities that hold for logic programming continue to hold for default theories. We show how the same technique may be applied to strong autoepistemic logic: the logic of strong expansions proposed by Marek and Truszczynski.     

溯因推理研究：现状与问题

在人类认识世界的过程中,现实的生存世界里会不时发生着一些“令人惊奇的”现象,为了理解和分析这个问题,人们所使用的解疑释惑的方法往往就是尝试寻找引起这些现象的原因是什么。例如早上醒来你发现路是湿的,你会猜测昨晚天下雨了。通俗地讲这种解释观测事实(或已知结果)的推理过程就是溯因(Abduction)。可以说类似的例子一直在我们的日常生活或者科学研究中重复着,以现实生活中的医学诊断为例,当医生了解了患者的病症后,他会根据自己对疾病和症状间因果关系方面的医学知识,推断出可能的病因是什么。对于自然科学研究也是如此,N.R.Hanson和C.S.Pierce曾分别论证说,当开普勒断言“火星的运行轨迹是椭圆的”的时候,他所使用的推理方法就是溯因。     

Experience with logical code analysis in software maintenance

Formal program specification and logical analysis are often used for program derivation and proofs of correctness. The basic tools include the logic of predicate calculus and Dijkstra's weakest precondition calculations. Recent work has shown that these tools are also very useful in the maintenance phase of the software life-cycle. This paper reports experience working with software maintenance teams to apply formal methods. Formal logical analysis is invaluable for isolating defects, determining code corrections, eliminating side-effects, and code re-engineering. Logical analysis works well in software maintenance because many defects can be isolated to small segments of code. These small segments can then be analyzed manually or with code analysis tools. The result is lowered software maintenance costs due to the benefits of defect prevention, reduction of code complexity metrics, productivity improvements, and better specifications and documentation. It would be beneficial to use logical code analysis in the earlier phases of the software life-cycle, such as quality assurance and inspection.     

Computing answers with model elimination

We demonstrate that theorem provers using model elimination (ME) can be used as answer-complete interpreters for disjunctive logic programming. More specifically, we introduce a family of restart variants of model elimination and we introduce a mechanism for computing answers. Building on this, we develop a new calculus called ancestry restart ME. This variant admits a more restrictive regularity restriction than restart ME and, as a side-effect, it is in particular attractive for computing definite answers. The presented calculi can also be used successfully in the context of automated theorem proving. We demonstrate experimentally that it is more difficult to compute nontrivial answers to goals than to prove the existence of answers.     

Dealing with logical omniscience: Expressiveness and pragmatics

We examine four approaches for dealing with the logical omniscience problem and their potential applicability: the syntactic approach, awareness, algorithmic knowledge, and impossible possible worlds. Although in some settings these approaches are equi-expressive and can capture all epistemic states, in other settings of interest (especially with probability in the picture), we show that they are not equi-expressive. We then consider the pragmatics of dealing with logical omniscience—how to choose an approach and construct an appropriate model.     

Reasoning with infinite stable models

This paper illustrates extensively the theoretical properties, the implementation issues, and the programming style underlying finitary programs. They are a class of normal logic programs whose consequences under the stable model semantics can be effectively computed, despite the fact that finitary programs admit function symbols (hence infinite domains) and recursion. From a theoretical point of view, finitary programs are interesting because they enjoy properties that are extremely unusual for a nonmonotonic formalism, such as compactness. From the application point of view, the theory of finitary programs shows how the existing technology for answer set programming can be extended from problem solving below the second level of the polynomial hierarchy to all semidecidable problems. Moreover, finitary programs allow a more natural encoding of recursive data structures and may increase the performance of credulous reasoners.     

Generative design in architecture using an expert system

The mathematician-architect Christopher Alexander has devised a theory of objective architectural design. He believes that all architectural forms can be described as interacting patterns, all possible relationships of which are governed by generative rules. These form a ‘pattern language’ capable of generating forms appropriate for a given environmental context. The complexity of interaction among these rules leads to difficulties in their representation by conventional methods. This paper presents a Prolog-based expert system which implements Alexander's design methodology to produce perspective views of partially and fully differentiated 3-dimensional architectural forms.     

Using SCL to specify and check design intent in source code

Software developers often fail to respect the intentions of designers due to missing or ignored documentation of design intent. SCL (Structural Constraint Language) addresses this problem by enabling designers to formalize and confirm compliance with design intent. The designer expresses his intent as constraints on the program model using the SCL language. The SCL conformance checking tool examines developer code to confirm that the code honors these constraints. This paper presents the design of the SCL language and its checker, a set of practical examples of applying SCL, and our experience with using it both in an industrial setting and on open-source software.     

A strategic model for supply chain design with logical constraints: formulation and solution

This paper proposes a strategic production–distribution model for supply chain design with consideration of bills of materials (BOM). Logical constraints are used to represent BOM and the associated relationships among the main entities of a supply chain such as suppliers, producers, and distribution centers. We show how these relationships are formulated as logical constraints in a mixed integer programming (MIP) model, thus capturing the role of BOM in the selection of suppliers in the strategic design of a supply chain. A test problem is presented to illustrate the effectiveness of the formulation and solution strategy. The results and their managerial implications are discussed.Scope and purposeSupply chain design is to provide an optimal platform for efficient and effective supply chain management. The problem is often an important and strategic operations management problem in supply chain management. This paper shows how the mixed integer programming modeling techniques can be applied to supply chain design problem, where some complicated relations, such as bills of materials, are involved. We discuss how to solve such a complicated model efficiently.     

Regulation management and logic programming

Regulations are pervasive in information systems. They manifest themselves as design rules, integrity constraints, deadlines, conventions, information disclosure requirements, policies, procedures, contracts, taxes, quotas and other statutes. Managing regulations is difficult. Regulations are complex, change frequently and rest on models of the real world that involve unusual vocabulary if not unusual concepts. Consequently, checking compliance with regulations is tedious and error-prone. Logic programming appears to provide a good framework for developing regulation management systems. Besides permitting arbitrary regulations to be modelled, it offers rapidity and ease of development, readability, incremental modifiability, extensibility and portability. These features are not provided by existing DP programming tools, database managers or conventional expert-system shells. This paper investigates the application of logic programming in a significant regulation management application: Workers' Compensation Insurance premium auditing. The insurance premium computation rules for the State of California were encoded as a large Prolog program. This application illustrates specific strengths and weaknesses of logic programming and Prolog in dealing with large-scale real-world regulations.     

RFuzzy: Syntax, semantics and implementation details of a simple and expressive fuzzy tool over Prolog

We present the RFuzzy framework, a Prolog-based tool for representing and reasoning with fuzzy information. The advantages of our framework in comparison to previous tools along this line of research are its easy, user-friendly syntax, and its expressivity through the availability of default values and types.In this approach we describe the formal syntax, the operational semantics and the declarative semantics of RFuzzy (based on a lattice). A least model semantics, a least fixpoint semantics and an operational semantics are introduced and their equivalence is proven. We provide a real implementation that is free and available. (It can be downloaded from http://babel.ls.fi.upm.es/software/rfuzzy/.) Besides implementation details, we also discuss some actual applications using RFuzzy.     

源代码中设计模式实例的抽取及验证方法研究

从源码中抽取设计模式对于提高软件可理解性和可维护性、软件设计重用以及软件重构具有重要意义。面向Java语言提出了一种静态和动态分析相结合的源码中设计模式的抽取方法。具体地,研究了源码中设计模式抽取的静态结构分析过程,为了进一步提高设计模式实例抽取的准确率,对结构分析得到的创建型模式候选,使用创建对象的多重性分析方法进行验证,对结构分析得到的行为型模式候选,使用动态分析的方法进行验证,以区分结构相似但行为不同的模式的实例。最后实现了设计模式抽取工具并对开源软件中的模式实例进行抽取。通过实验数据,验证了设计模式实例抽取及验证方法的可行性及有效性。     

基于语法和语义结合的源代码精确搜索方法

针对在编写软件、复用源代码的过程中仅依靠关键词无法精准搜索到适用源代码的问题,提出一种将语法和语义结合的源代码精准搜索方法。首先依据源代码语法语义的客观和唯一性,增加语法结构和"输入/输出"语义作为用户录入请求的一部分,并规范了具体的请求格式;然后在此基础上分别设计源代码语法匹配算法、"输入/输出"语义匹配算法、关键词兼容匹配,以及源代码搜索结果可信度计算算法;最后综合上述算法实现对源代码的精准搜索。测试结果表明：与单纯的关键词搜索相比,提出的方法对搜索的平均排序倒数（MRR）有超过62%的提升,有助于实现源代码的精准搜索。     

An illustrative example of refactoring object‐oriented source code with aspect‐oriented mechanisms

This paper describes a refactoring process that transforms a Java source code base into a functionally equivalent AspectJ source code base. The process illustrates the use of a collection of refactorings for aspect‐oriented source code, covering the extraction of scattered implementation elements to aspects, the internal reorganization of the extracted aspects and the extraction of commonalities to super‐aspects. Copyright © 2007 John Wiley & Sons, Ltd.     

Repairing and reasoning with inconsistent and uncertain ontologies

With the development of semantic web, the quality and correctness of ontologies play more and more important roles in semantic representation and knowledge sharing. However, ontologies are often inconsistent and uncertain in real situations. Because of the difficulty in ensuring the quality of ontologies, there is an increasing need for dealing with the inconsistency and uncertainty in real-world applications of ontological reasoning and management. This paper adopts two methods to handle the inconsistent and uncertain ontologies: the first one is to repair the inconsistency, algorithms RIO and RIUO are proposed to compute the candidate repair set, the consistency of ontology could be recovered through deleting or modifying the axioms in candidate repair set; the second one is to develop a non-standard reasoning method to obtain meaningful answers, algorithms RMU and RMIU are proposed to perform query-specific reasoning methods for inconsistent and uncertain ontologies without changing the original ontologies. Finally the prototype system is constructed and the experiment results validate the usability and effectiveness of our approaches.     

RS码技术在PDF417码纠错码编译码中的应用研究

在引入RS码编译码原理的基础上,通过对二维条码PDF417码和四一七国家条码规范的分析和研究,将RS码技术应用到PDF417码纠错码的编码、译码算法过程中,完成了PDF417纠错的实现,同时给出了在GF（929）域中计算3的幂值的方法,解决了中间结果过大导致数据溢出的问题。为PDF417码的纠错码提供了一个完整的解决方案。     

P³: a code and design conventions preprocessor for Java

One of the techniques employed by programmers during the development process is the use of code and design conventions. These are rules‐of‐thumb or best practices that improve the maintainability of software applications. In general, these conventions are maintained manually by the programmer since automated support is usually restricted to the automatic generation of code. However, the late discovery of convention errors can result in significant costs due to the effort required to correct them. In order to facilitate the early detection of these errors, the Practical Preprocessor for Programming Conventions system, P³ (pronounced P3),is proposed. This tool acts as a preprocessor to the Java compiler by providing facilities for the maintenance of specific object‐oriented code conventions and design principles during the creation of Java programs. This paper presents the design and implementation of the P³ system and also the practical experience of using this facility in a University programming environment. Copyright © 2002 John Wiley & Sons, Ltd.