Prolog/Rex inference engine

Abstract: Prolog/Rex supports the construction of knowledge-based systems, allowing frames (Prolog/Rex concepts) and rules to be combined, and providing language level support for hypothetical reasoning and assumption-based truth maintenance (Prolog/Rex viewpoint mechanism). To increase run-time performance during rule execution, Prolog/Rex provides two complementary rule compilation techniques: the simple indexing scheme and the heavily modified Rete expansion method. To improve the efficiency of the inference engine, we built an agenda-based rule manager that uses priority mechanism and/or heuristics embedded in meta-rules to control the rule firing order. Forward- and backward-chaining can be combined within the same program.     

Discovering R-rules with a directed hierarchy

In this paper, we extend the classical notion of quasi-implication (“when a_i is present then usually a_j is also present”) to R-rules (rules of rules), the premisses and the conclusions of which can be rules themselves. A new statistical measure, based on the implicative intensity defined by Gras for quasi-implications, is defined to assess the significance of R-rules on a data set. We show how to organize R-rules in a new combinatorial structure, the directed hierarchy, which is inspired by the classical hierarchical classification. An incremental algorithm is developed to find the most significant R-rule “amalgamation”. An illustration is presented on a real data set stemming from a recent survey of the French Public Education Mathematical Teacher Society on the level in mathematics of pupils in the final year of secondary education and the perception of this subject.     

Managing Conflicts between Rules

Rules are used as a programming paradigm in several application domains, including active databases, planning, expert systems, and billing. For example, active databases have rules that execute upon the occurrence of particular events if specified condition predicates are satisfied. It is often the case that multiple rules are fireable when a particular event occurs. We propose a declarative mechanism to control the interaction and execution of multiple rules. The mechanism is based upon logical meta-rules that can express various types of relationships between rules. The meta-rules allow us to reason statically about the rule behavior. We can determine, in polynomial time, whether a rule will never execute, whether two rules can ever be executed together, and whether a rule system is guaranteed to have a unique execution set for all possible rules that become fireable. In this paper, we illustrate our techniques using rules in an active database. A system based upon the meta-rules and the static analysis presented here has been found to be of value in a billing application at AT & T to control interactions between discount plans.     

Rules and Principles in Legal Reasoning. A Study of Vagueness and Collisions in Artificial Intelligence and Law

There is a difference between rules and principles in Law Argumentation Theory. The conflict of rules is solved by meta-rules like Lex Superior (based in general hierarchical structure of legal system), Lex Posterior (based on later rule priority), Lex Specialis (based on specification of rules) and also by exceptions, which exclude the conflict. The collisions of rules imply the validity negation of one rule. However, this does not occur in a collision of principles. Even when one principle is not applied by collisions, its validity remains. Another point is that the priority could change, changing the overridden principle. So, it is necessary to build a reasoning model that allows reasoning with conflicting legal principles. Another problem is vagueness of principles. Vagueness does not mean just an imprecise meaning, linguistically talking. There should be attributed a semantic, or a pragmatic meaning. Vagueness of principles occurs on account of its opened antecedent, with no established conduct. In this paper a model of reasoning using Artificial Intelligence (AI) & Law methods is described aiming at treating vagueness and collisions of principles, searching to establish rationality in legal argumentation systems.     

Fuzzy prolog

Various methods of representing uncertainty are discussed including some fuzzy methods. Representation and calculation of fuzzy expressions are discussed and a symbolic representation of fuzzy quantities coupled with axiomatic evaluation is proposed. This is incorporated into the PROLOG language to produce a fuzzy version. Apart from enabling imprecise facts and rules to be expressed, a natural method of controlling the search is introduced, making the search tree admissible.Formal expression of heuristic information in the same language, FUZZY PROLOG, as the main problem language follows naturally and therefore allows the same executor to evaluate in both “problem” space and “heuristic” space.In addition, the use of variable functors in the specification of bidirectional logic is discussed. The paper shows two areas of application of higher order fuzzy predicates. As an introduction Warren's examples are outlined and used with variable functors to illustrate their use in describing some relatively conventional applications.Translation of English into horn clause format is described and is used to illustrate the simplicity of representation using variable functors. Alternative formulations are also explored, typically the use of the “meta-variable” in MICRO-PROLOG and using the “univ” operator.Representation of rule generation and inference is addressed. Examples are given where the expression of meta-rules in standard PROLOG are compared with the expression of the same rules using “variable” predicate symbols. Some meta-rules illustrated are clearly not universally valid and this leads to the addition of fuzzy tokens.     

基于C-BRB模型的发动机运行状态监测方法

针对发动机运行状态监测过程中发动机内部多个因素之间相关性与建模方法可解释性问题,提出数据驱动下C-BRB方法。该方法首先通过样本数据计算发动机内部多个因素之间的Kendall秩相关系数,并确定具体Copula模型及参数λ,实现对多个因素之间相关性的测量;然后使用置信规则库(BRB)对发动机内部多个因素建模,在BRB推理过程中,每条激活规则的综合匹配度由Copula模型对该规则中各前提属性的匹配度进行计算得到,并利用证据推理(ER)算法对所有激活规则进行融合得到输出。实例结果表明,所提方法在推理发动机传感器数据上具有较高的精度。     

Rewriting with Equivalence Relations in ACL2

Traditionally, a conditional rewrite rule directs replacement of one term by another term that is provably equal to it, perhaps under some hypotheses. This paper generalizes the notion of rewrite rule to permit the connecting relation to be merely an equivalence relation. We then extend the algorithm for applying rewrite rules. Applications of these generalized rewrite rules are only admissible in certain equivalential contexts, so the algorithm tracks which equivalence relations are to be preserved and admissible generalized rewrite rules are selected according to this context. We introduce the notions of congruence rule and refinement rule. We also introduce the idea of generated equivalences, corresponding to a new equivalence relation generated by a set of pre-existing ones. Generated equivalences are used to give the rewriter broad access to admissible generalized rewrite rules. We discuss the implementation of these notions in the ACL2 theorem prover. However, the discussion does not assume familiarity with ACL2, and these ideas can be applied to other reasoning systems as well.     

基于规则引擎的通讯卫星应急任务调度

为降低调度规则变动对独占资源通讯卫星应急任务调度系统的影响,提高系统的灵活性、可扩展性及易维护性,提出一种基于规则引擎的独占资源通讯卫星应急任务调度方法,运用规则引擎技术实现调度规则与业务逻辑代码的解耦。通过研究独占资源通讯卫星应急任务调度策略,设计应急任务调度规则,结合Drools规则语法建立调度规则库。在Rete算法节点共享机制研究的基础上,设计基于权重的节点连接方法,改进推理网的构建过程,优化推理网的结构。实验结果表明,基于改进后的规则引擎的调度系统拥有更好的运行效率。     

基于语义Web规则的软件体系结构

针对目前软件系统面向大规模和复杂业务处理的要求,研究对业务流程和逻辑进行形式化的逻辑描述和逻辑处理,引入Mandarax规则引擎进行业务逻辑的推理处理,实现业务逻辑的集中处理。作为一个可复用的系统构架设计的基于规则的软件体系结构,使用Prova建立规则层,利用规则引擎实现业务逻辑的推理处理,通过规则层应用实验的实现证明基于规则的软件系统结构的可行性和有效性,在一定程度上完善了软件工程设计技术的理论层次。     

On rules with existential variables: Walking the decidability line

We consider positive rules in which the conclusion may contain existentially quantified variables, which makes reasoning tasks (such as conjunctive query answering or entailment) undecidable. These rules, called ??-rules, have the same logical form as tuple-generating dependencies in databases and as conceptual graph rules. The aim of this paper is to provide a clearer picture of the frontier between decidability and non-decidability of reasoning with these rules. Previous known decidable classes were based on forward chaining. On the one hand we extend these classes, on the other hand we introduce decidable classes based on backward chaining. A side result is the definition of a backward mechanism that takes the complex structure of ??-rule conclusions into account. We classify all known decidable classes by inclusion. Then, we study the question of whether the union of two decidable classes remains decidable and show that the answer is negative, except for one class and a still open case. This highlights the interest of studying interactions between rules. We give a constructive definition of dependencies between rules and widen the landscape of decidable classes with conditions on rule dependencies and a mixed forward/backward chaining mechanism. Finally, we integrate rules with equality and negative constraints to our framework.     

General purpose inference engine for canonical graph models

The design and implementation of a General Purpose Inference Engine for canonical graph models that is both flexible and efficient is addressed. Conventional inference techniques (e.g. forward chaining, backward chaining and mixed strategies) are described, and new modes of flexibility through the provision of inexact matching between data and assertions/rules are explained. In GPIE, scanning/searching of the rules in the rule base is restricted to a minimum during execution, but at the expense of compilation of the rule set prior to execution. The generality of the rule set is transparent to the inference engine, thereby permitting reasoning at various levels. This research demonstrates that a graph-based inference engine offering flexible control structures and inxact matching can complement intermediate notations, such as conceptual graphs, offering the expressive power of a rich knowledge representation formalism. The availability of an extendible graph processor for building appropriate canonical graph models presents the exciting prospect of a general purpose reasoning engine.     

PARULEL: Parallel rule processing using meta-rules for redaction

Although the problem of increasing the speed of rule-based programs has been studied for a long while, so far the level of parallelism achieved under various parallel processing schemes fails to meet expectations of high performance gains. Most of the work has focused on manipulating existing rule programs to accommodate parallel architectures. However, without changing the inherently sequential algorithms encoded in rule form and without using intrinsic parallel rule languages to exploit parallelism, speedup is severely limited. In this paper we demonstrate that to maximize parallelism, manipulations must take place at the algorithmic level in addition to the program level. However, traditional rule languages are not equipped to easily express parallel algorithms. Thus, an inherently parallel rule language must be devised to enable maximum parallelism. We present our initial specification of such a language, named PARULEL. Preliminary performance results are detailed for one test case program. PARULEL is one part of a larger research effort that considers four key approaches to parallel rule processing: inherently parallel execution semantics; the use of redaction meta-rules to allow programmer control of the set of parallel instantiations; an incremental evaluation algorithm that incorporates, in an efficient manner, updates to the initial set of assumptions; and an algorithm that maps a program to a parallel architecture.     

DLEJena: A practical forward-chaining OWL 2 RL reasoner combining Jena and Pellet

This paper describes DLEJena, a practical reasoner for the OWL 2 RL profile that combines the forward-chaining rule engine of Jena and the Pellet DL reasoner. This combination is based on rule templates, instantiating at run-time a set of ABox OWL 2 RL/RDF Jena rules dedicated to a particular TBox that is handled by Pellet. The goal of DLEJena is to handle efficiently, through instantiated rules, the OWL 2 RL ontologies under direct semantics, where classes and properties cannot be at the same time individuals. The TBox semantics are treated by Pellet, reusing in that way efficient and sophisticated TBox DL reasoning algorithms. The experimental evaluation shows that DLEJena achieves more scalable ABox reasoning than the direct implementation of the OWL 2 RL/RDF rule set in the Jena’s production rule engine, which is the main target of the system. DLEJena can be also used as a generic framework for applying an arbitrary number of entailments beyond the OWL 2 RL profile.     

Hybrid

Combining higher-order abstract syntax and (co)-induction in a logical framework is well known to be problematic. We describe the theory and the practice of a tool called Hybrid, within Isabelle/HOL and Coq, which aims to address many of these difficulties. It allows object logics to be represented using higher-order abstract syntax, and reasoned about using tactical theorem proving and principles of (co)induction. Moreover, it is definitional, which guarantees consistency within a classical type theory. The idea is to have a de Bruijn representation of λ-terms providing a definitional layer that allows the user to represent object languages using higher-order abstract syntax, while offering tools for reasoning about them at the higher level. In this paper we describe how to use Hybrid in a multi-level reasoning fashion, similar in spirit to other systems such as Twelf and Abella. By explicitly referencing provability in a middle layer called a specification logic, we solve the problem of reasoning by (co)induction in the presence of non-stratifiable hypothetical judgments, which allow very elegant and succinct specifications of object logic inference rules. We first demonstrate the method on a simple example, formally proving type soundness (subject reduction) for a fragment of a pure functional language, using a minimal intuitionistic logic as the specification logic. We then prove an analogous result for a continuation-machine presentation of the operational semantics of the same language, encoded this time in an ordered linear logic that serves as the specification layer. This example demonstrates the ease with which we can incorporate new specification logics, and also illustrates a significantly more complex object logic whose encoding is elegantly expressed using features of the new specification logic.     

On semantic resolution with lemmaizing and contraction and a formal treatment of caching

Reducing redundancy in search has been a major concern for automated deduction. Subgoal-reduction strategies, such as those based on model elimination and implemented in Prolog technology theorem provers, prevent redundant search by usinglemmaizing andcaching, whereas contraction-based strategies prevent redundant search by usingcontraction rules, such assubsumption. In this work we show that lemmaizing and contraction can coexist in the framework ofsemantic resolution. On the lemmaizing side, we define two meta-level inference rules for lemmaizing in semantic resolution, one producing unit lemmas and one producing non-unit lemmas, and we prove their soundness. Rules for lemmaizing are meta-rules because they use global knowledge about the derivation, e.g. ancestry relations, in order to derive lemmas. Our meta-rules for lemmaizing generalize to semantic resolution the rules for lemmaizing in model elimination. On the contraction side, we give contraction rules for semantic strategies, and we define apurity deletion rule for first-order clauses that preserves completeness. While lemmaizing generalizes success caching of model elimination, purity deletion echoes failure caching. Thus, our approach integrates features of backward and forward reasoning. We also discuss the relevance of our work to logic programming. Supported in part by the National Science Foundation with grant CCR-94-08667 and CCR-97-01508. Supported in part by grant NSC 86-2213-E-002-047 and NSC 87-2213-E-002-029 of the National Science Council of the Republic of China. Maria Paola Bonacina, Ph.D.: She is on the faculty of the Department of Computer Science of the University of Iowa. She received a laurea (1986) and a doctorate in informatics from the Universita degli Studi di Milano, and a Ph.D. in computer science from the State University of New York at Stony Brook (1992). She was awarded fellowships by the Universita degli Studi di Milano, the European Union and the General Electric Foundation. The unifying theme of her research is automated theorem proving. Her research areas include distributed automated deduction, the theory of search and strategy analysis, completion-based theorem proving, category theory for computer science, term rewriting systems, logic programming, and manyvalued logic. Jieh Hsiang, Ph.D.: He is a Professor of Computer Science at the National Taiwan University and is also the Director of the Center of Excellence for Research in Computer Systems of the National Taiwan University. Professor Hsiang is known for work in term rewriting systems and automated deduction. His other research interests include logic programming, programming logics, computer viruses, and intelligent agents. Recently he has also become interested in the digitization of Taiwanese and Chinese historical records and heritage. Professor Hsiang received a B.S. degree in mathematics from National Taiwan University in 1976 and a Ph.D. degree in computer science from the University of Illinois at Urbana-Champaign in 1982. Before returning to Taiwan in 1993, he was a Professor of Computer Science at the State University of New York st Stony Brook.     

A Computational Framework for Practical Social Reasoning

This article describes a framework for practical social reasoning designed to be used for analysis, specification, and implementation of the social layer of agent reasoning in multiagent systems. Our framework, called the expectation strategy behavior (ESB) framework, is based on (i) using sets of update rules for social beliefs tied to observations (so‐called expectations), (ii) bounding the amount of reasoning to be performed over these rules by defining a reasoning strategy, and (iii) influencing the agent's decision‐making logic by means of behaviors conditioned on the truth status of current and future social beliefs. We introduce the foundations of ESB conceptually and present a formal framework and an actual implementation of a reasoning engine, which is specifically combined with a general (belief–desire–intention‐based) practical reasoning programming system. We illustrate the generality of ESB through select case studies, which show that it is able to represent and implement different typical styles of social reasoning. The broad coverage of existing social reasoning methods, the modularity that derives from its declarative nature, and its focus on practical implementation make ESB a useful tool for building advanced socially reasoning agents.     

大规模定制下基于本体的服务产品配置研究*

为了研究服务产品大规模定制的实现,探讨了服务产品大规模定制的实现机理和关键技术,指出模块化设计对服务产品族及服务产品平台的重要性。在服务产品模块化设计的基础上,为了提高服务产品配置知识的共享性和重用性,提出了一般服务产品配置的模型和概念,结构化了服务产品配置的构件和模块,建立了服务产品配置本体。采用网络本体语言OWL形式化服务产品配置的结构知识,采用语义网规则语言SWRL编码服务产品配置的约束知识,并分别映射到JESS推理系统的知识库和规则库中,使用JESS推理机执行推理过程,产生配置结果。为说明该方法的     

The IKBALS project: Multi-modal reasoning in legal knowledge based systems

In attempting to build intelligent litigation support tools, we have moved beyond first generation, production rule legal expert systems. Our work integrates rule based and case based reasoning with intelligent information retrieval.When using the case based reasoning methodology, or in our case the specialisation of case based retrieval, we need to be aware of how to retrieve relevant experience. Our research, in the legal domain, specifies an approach to the retrieval problem which relies heavily on an extended object oriented/rule based system architecture that is supplemented with causal background information. We use a distributed agent architecture to help support the reasoning process of lawyers.Our approach to integrating rule based reasoning, case based reasoning and case based retrieval is contrasted to the CABARET and PROLEXS architectures which rely on a centralised blackboard architecture. We discuss in detail how our various cooperating agents interact, and provide examples of the system at work. The IKBALS system uses a specialised induction algorithm to induce rules from cases. These rules are then used as indices during the case based retrieval process.Because we aim to build legal support tools which can be modified to suit various domains rather than single purpose legal expert systems, we focus on principles behind developing legal knowledge based systems. The original domain chosen was theAccident Compensation Act 1989 (Victoria, Australia), which relates to the provision of benefits for employees injured at work. For various reasons, which are indicated in the paper, we changed our domain to that ofCredit Act 1984 (Victoria, Australia). This Act regulates the provision of loans by financial institutions.The rule based part of our system which provides advice on the Credit Act has been commercially developed in conjunction with a legal firm. We indicate how this work has lead to the development of a methodology for constructing rule based legal knowledge based systems. We explain the process of integrating this existing commercial rule based system with the case base reasoning and retrieval architecture.     

Generalized one-sided forbidding grammars

In generalized one-sided forbidding grammars (GOFGs), each context-free rule has associated a finite set of forbidding strings, and the set of rules is divided into the sets of left and right forbidding rules. A left forbidding rule can rewrite a nonterminal if each of its forbidding strings is absent to the left of the rewritten symbol. A right forbidding rule is applied analogically. Apart from this, they work like any generalized forbidding grammar. This paper proves the following three results. (1) GOFGs where each forbidding string consists of at most two symbols characterize the family of recursively enumerable languages. (2) GOFGs where the rules in one of the two sets of rules contain only ordinary context-free rules without any forbidding strings characterize the family of context-free languages. (3) GOFGs with the set of left forbidding rules coinciding with the set of right forbidding rules characterize the family of context-free languages.