Prolog/Rex-a way to extend Prolog for better knowledgerepresentation

Prolog/Rex represents a powerful amalgamation of the latest techniques for knowledge representation and processing, rich in semantic features that ease the difficult task of encoding heterogeneous knowledge of real-world applications. The Prolog/Rex concept mechanism lets a user represent domain entities in terms of their structural and behavioral properties, including multiple inheritance, arbitrary user-defined relations among entities, annotated values (demons), incomplete knowledge, etc. A flexible rule language helps the knowledge engineer capture human expertise and provide flexible control of the reasoning process. Additional Prolog/Rex strength that cannot be found in any other hybrid language made on top of Prolog is language level support for keeping many potentially contradictory solutions to a problem, allowing possible solutions and their implications to be automatically generated and completely explored before they are committed. The same mechanism is used to model time-states, which are useful in planning and scheduling applications of Prolog/Rex     

Algebraic computational models of OR-parallel execution of Prolog

A specification of the OR-parallel execution of Prolog programs, using CHOCS (calculus of higher order communicating systems) [24], is presented in the paper. A translation is defined from Prolog programs and goals to CHOCS processes: the execution of the CHOCS process corresponding to a goal mimics the OR-parallel execution of the original Prolog goal. In the translation, clauses and predicate definitions of a Prolog program correspond to processes. To model OR-parallelism, the processes , corresponding to clauses (having the same head predicate ) start their execution concurrently, but, in order to respect the depth-first search rule, each is guarded by the termination of the executions of processes 's, . The computational model is proved correct with respect to the semantics of Prolog, as given in [4, 5]. Our model, because of its algebraic specification, can be easily used to prove properties of the parallel execution of Prolog programs. Moreover, the model exploits the maximum degree of parallelism, by giving the Prolog solutions in parallel, without any order among them. However, this model, being close to the Prolog semantics definition, contains sources of inefficiency which make it unpractical as a guide for the implementation. To overcome these problems, a new computational model is defined. This model is obtained by modifications of the basic one and thus its correctness can be easily proved. Finally, we show how to obtain models of different real implementations of OR-parallel Prolog by slight modification of the new model. The relations among all these models, in terms of parallelism degree, are studied by using the concepts of bisimulation and simulation, developed for concurrent calculi. Received: 5 May 1995 / 28 May 1996     

Automatic inductive theorem proving using prolog

Although Prolog is a programming language based on techniques from theorem proving, its use as a base for a theorem prover has not been explored until recently (Stickel, 1984). In this paper, we introduce a Prolog-based deductive theorem proving method for proving theorems in a first-order inductive theory representable in Horn clauses. The method has the following characteristics:

• 1.It automatically partitions the domains over which the variables range into subdomains according to the manner in which the predicate symbols in the theorem are defined.
• 2.For each of the subdomains the prover returns a lemma. If the lemma is true, then the target theorem is true for this subdomain. The lemma could also be an induction hypothesis for the theorem.
• 3.The method does not explicitly use any inductive inference rule. The induction hypothesis, if needed for a certain subdomain, will sometimes be generated from a (limited) forward chaining mechanism in the prover and not from employing any particular inference rule.

In addition to the backward chaining and backtracking facilities of Prolog, our method introduces three new mechanism—skolemization by need, suspended evaluation, and limited forward chaining. These new mechanisms are simple enough to be easily implemented or even incorporated into Prolog. We describe how the theorem prover can be used to prove properties of Prolog programs by showing two simple examples.     

A full theorem-prover under uncertainty

Prolog embodies an ordered input resolution inference mechanism, with a powerful unification procedure. However, Prolog is not a full theorem-prover, and does not contain an inexact reasoning mechanism. In this paper, it is shown how these capabilities can be combined in a Prolog environment. A Prolog meta-interpreter is used in an elegant and simple way for this purpose. The inexact reasoning mechanism is presented through the certainty factor model, but it is also discussed how other inexact reasoning models may be also implemented.     

基于规则的公交识别专家系统设计与实现

通过对专家系统模型的分析,详细设计了基于规则的公交识别专家系统的构造模块,并根据专家系统的目标创建了事实库和规则库。在规则库的创建中,改进了规则的线性推理机制,提出递归调用规则：利用递归调用形式的规则库实现了两站间直达、N次中转可达路径的查找问题,并实现了两站路径的最小耗费计算。最后通过Visual Prolog 7.3,验证实验结果,得出实验结论。     

Translating production rules into a forward reasoning Prolog program

Several attempts have been made to design a production system using Prolog. To construct a forward reasoning system, the rule interpreter is often written in Prolog, but its execution is slow. To develop an efficient production system, we propose a rule translation method where production rules are translated into a Prolog program and forward reasoning is done by the translated program. To translate the rules, we adopted the technique developed in BUP, the bottom-up parsing system in Prolog. Man-machine dialogue functions were added to the production system and showed the potential of our method to be applied to expert systems.     

一种基于PROLOG的ES建造工具库的研究与实现

本文描述了一基于ＰＲＯＬＯＧ的专家系统建造工具库ＰＴＥＳ的实验系统。ＰＴＥＳ是用ＰＲＯＬＯＧ编写的，该系统根据支持基于规则的知识表示及近似推理对ＰＲＯＬＯＧ的知识处理能力进行了扩充。ＰＴＥＳ的推理机制使用了可能性逻辑及模糊集合理论作为其逻辑基础并以一种形式化的方法提供了处理非确定事实及非确定规则的能力。     

An application of structural modeling and automated reasoning to real-time systems design

This paper presents an application of structural modeling and automated reasoning as a software development environment for real-time systems. This application satisfies two major requirements for such an environment: (1) to synthesize an absolutely correct program and, (2) to increase software productivity. The real-time systems, which consist of concurrent programs, are described by a Prolog based concurrent object-oriented language, called MENDEL/87. As a typical concurrent program consists of two parts: functional and synchronization parts; the functional part in the reusable component to be registered in a library will be generated by a structural modeling through the use of structuring functions with respect to data flows. The synchronization part will be synthesized from temporal logic specifications by the use of an automated reasoning mechanism. This paper also describes the MENDELS ZONE implemented on a Prolog machine, which is the working base for the presented application method.     

On the completeness of naive memoing in Prolog

Memoing is often used in logic programming to avoid redundant evaluation of similar goals, often on programs that are inherently recursive in nature. The interaction between memoing and recursion, however, is quite complex. There are several top-down evaluation strategies for logic programs that utilize memoing to achieve completeness in the presence of recursion. This paper’s focus, however, is on the use ofnaive memoing in Prolog. Using memoingnaively in conjunction with recursion in Prolog may not produce expected results. For example, adding naive memoing to Prolog’s evaluation of a right-recursive transitive closure may be incomplete, whereas adding naive memoing to Prolog’s evaluation of a left-recursive transitive closure may be terminating and complete. This paper examines the completeness of naive memoing in linear-recursive, function-free logic programs evaluated with Prolog’s top-down evaluation strategy. In addition, we assume that the program is definite and safe, having finite base relations and exactly one recursive predicate. The goal of the paper is a theoretical study of the completeness of naive memoing and recursion in Prolog, illustrating the limitations imposed even for this simplified class of programs. The naive memoing approach utilized for this study is based on extension tables, which provide a memo mechanism with immediate update view semantics for Prolog programs, through a source transformation known as ET. We introduce the concept ofET-complete, which refers to the completeness of the evaluation of a query over a Prolog program that memos selected predicates through the ET transformation. We show that left-linear recursions defined by a single recursive rule are ET-complete. We generalize the class of left-linear recursions that are ET-complete by introducing pseudo-left-linear recursions, which are also defined by a single linear recursive rule. To add left-linear recursions defined bymultiple linear recursive rules to the class of ET-complete recursions, we present a left-factoring algorithm that converts left-linear recursions defined by multiple recusive rules into pseudo-left-linear recursions defined by a single recursive rule. Based on these results, the paper concludes by identifying research directions for expanding the class of Prolog programs to be examined in future work. This work was partially supported by the National Science Foundation under Grant CCR-9008737. Suzanne Wagner Dietrich, Ph.D.: She is an Associate Professor in the Department of Computer Science and Engineering at Arizona State University. Her research emphasis is on the evaluation of declarative logic programs especially in the context of deductive databases, including materialized view maintenance and condition monitoring in active deductive databases. More recently, her research interests include the integration of active, object-oriented and deductive databases as well as the application of this emerging database technology to various disciplines such as software engineering. She received the B. S. degree in computer science in 1983 from the State University of New York at Stony Brook, and as the recipient of an Office of Naval Research Graduate Fellowship, earned her Ph.D. degree in computer science at Stony Brook in 1987. Changguan Fan, M.S.: He is a Ph.D. candidate in the Department of Computer Science and Engineering at Arizona State University and a software engineer at the Regenisys Corporation in Scottsdale, AZ. His research interests include the evaluation of logic programs, deductive database systems and database management systems. He received his B.S. in Computer Science from the Shanghai Institute of Railway Technology, Shanghai, China in 1982 and his M.S. in the Department of Computer Science and Engineering at Arizona State University in 1989.     

Oriented equational clauses as a programming language

In the Prolog language, Horn clauses of first-order logic are regarded as programs, and the resolution procedure is used as an interpreter. In this paper, we present the formalism of Horn oriented equational clauses (Horn clauses with a rewrite rule as the head part, and a list of equations as the body part). We show that such a formalism can be interpreted as a logic language with built-in equality, and that a procedure based on clausal superposition can be used as an interpreter. We define the operational, model-theoretic and fixpoint semantics of the language, and prove their equivalence. Then we point out the advantages of such a programming language: embodying Prolog, mixing functional and relational features and, handling the equality relation. Lastly, we present experiments performed with an implemented interpreter.     

A rule-based procedure for generating programmable logic controller code from graphical input in the form of ladder diagrams

This paper is concerned with a procedure for the automatic generation of code for programmable logic controllers. Input to the procedure is data from a graphical model of the discrete event dynamic system which is to be implemented. The model is constructed in the form of a ladder diagram at a graphics workstation. The data are held as Prolog tuples, and Prolog is used in the procedure to implement a rule base through which the data are mapped into the programmable logic controller code. Underlying the rule base are two methodologies. The first is a top-down decomposition of the ladder diagram to a level of three basic structures. The second is a bottom-up integration of code based on these structures into code for the whole system. An example is used throughout and the approach is shown to be effective.     

结合C++与Prolog语言快速开发专家系统

文章论证了在专家系统三要素的开发及不同的开发阶段中应配合使用C++与Prolog以互补优势,分析当前常用的Prolog版本的特点并选择适用版本为研究对象。结合程序实例论述Prolog程序与C++程序的双向连接技术,为快速开发专家系统打下技术基础。     

A prolog technology theorem prover: Implementation by an extended prolog compiler

A Prolog technology theorem prover (PTTP) is an extension of Prolog that is complete for the full first-order predicate calculus. It differs from Prolog in its use of unification with the occurs check for soundness, the model-elimination reduction rule that is added to Prolog inferences to make the inference system complete, and depth-first iterative-deepening search instead of unbounded depthfirst search to make the search strategy complete. A Prolog technology theorem prover has been implemented by an extended Prolog-to-LISP compiler that supports these additional features. It is capable of proving theorems in the full first-order predicate calculus at a rate of thousands of inferences per second.This is a revised and expanded version of a paper presented at the 8th International Conference on Automated Deduction, Oxford, England, July 1986.This research was supported by the Defense Advanced Research Projects Agency under Contract N00039-84-K-0078 with the Naval Electronic Systems Command and by the National Science Foundation under Grant CCR-8611116. The views and conclusions contained herein are those of the author and should not be interpreted as necessarily representing the official policies, either expressed or implied, of the Defense Advanced Research Projects Agency, the National Science Foundation, or the United States government. Approved for public release. Distribution unlimited.     

Prolog versus Kee — A case study

The selection of the software development tool for the development of an expert system is a difficult and often disputed decision. This paper describes a comparison of a knowledge engineering tool, Kee, and a general purpose language, Prolog, on concrete and real life example from AGATHA, an electronic circuit board diagnosis expert system.Prolog is a high-level programming language with flexible and powerful inference mechanisms. Kee is a big tool that supports a frame-based knowledge representation, an object-oriented programming style and a built-in rule system. It also offers a window environment suitable for rapid development of user-interface prototypes.Prolog's representation is more succinct, implicit and uses problem specific predicates and therefore leaves more room for personal programming styles. Kee is more verbose, explicit and uses standard templates. The maintainability of a Prolog implementation relies heavily on good documentation. In Kee, the unavoidable ‘escapes to Lisp’ require a maintainer to be fluent in Kee and Lisp.Both Prolog and Kee require a considerable investment in learning time.     

LOGICAL EMBEDDED PUSH-DOWN AUTOMATA IN TREE-ADJOINING GRAMMAR PARSING

This paper extends the "parsing as deduction" approach to tree-adjoining grammars by showing how a TAG recognition problem can be reduced to a Datalog deduction problem, and presents an SLD selection rule that makes the proof search correspond to a top-down parse using the original grammar. Just as in the DCG extension of context-free grammars, this approach permits nodes to be labeled with firsl-order terms (rather than only atomic symbols). Finally the paper discusses implementation matters, and describes how the control rule can be efficiently implemented in Prolog.     

An application of an OR-Parallel Prolog system to phylogenetic analysis

In this paper we discuss an application of our OR-Parallel Prolog system to a search problem of importance in practice: the construction of phylogenetic trees. The use of a maximum likelihood method to construct such trees is based on concrete models of evolutional processes and is well-motivated statistically. However, the use of maximum likelihood methods has been hindered by the computational cost to calculate the likelihood of possible alternative trees (i.e. their confidence scores) at each search step for the optimal tree. To cope with this problem, we used OR-parallel Prolog as a coordination language to orchestrate the search for the optimal tree. A numerical computation written in C computed the likelihood of each alternative tree and a symbolic computation written in Prolog performed a parallel A* tree search. For constructing phylogenetic trees of bacterial organisms, our parallel algorithm allowed us to increase the size of the search space, allowing us to include nearly optimal as well as optimal intermediate trees in the search. Our priority mechanism reduced the generation of useless tasks and resulted in superlinear speedups in some cases.     

Automatic generation of MPEG test streams from high-level grammars

This paper describes a technique to generate complex, moving picture experts group (MPEG) data streams containing packets which range through a selected set of variants, as allowed by the grammar of the packet stream. The Prolog logic programming language has been used, whose declarative power allows data generation almost directly from the grammar, i.e. without the need for explicitly programming a grammar traversal mechanism as would be the case with an imperative language. A reasonably declarative style of grammar and variation definition is achieved, and at the same time, a reasonably efficient generation process. The basic idea is to use a declarative fragment of Prolog for the grammar, but to use imperative features of Prolog for matters like packet enumeration and packet payload generation. Generation of test data from grammars is not new, nor is the use of Prolog programs for generation of test data, but as far as we know, the combination of both has not reported on in the literature, nor its application to MPEG demultiplexers/decoders.     

The Prolog not-predicate and negation as failure rule

Clark’s query evaluation procedure for computing negative information in deductive databases using a “negation as failure” inference rule requires a safe computation rule which may only select negative literals if they are ground. This is a very restrictive condition, which weakens the usefulness of negation as failure in a query evaluation procedure. This paper studies the definition and properties of the “not” predicate defined in most Prolog systems which do not enforce the above mentioned condition of a safe computation rule. We show that the negation in clauses and the “not” Predicate of Prolog are not the same. In fact a Prolog program may not be in clause form. An extended query evaluation procedure with an extended safe computation rule is proposed to evaluate queries which involve the “not” predicate. The soundness and completeness of this extended query evaluation procedure with respect to a class of logic programs are proved. The implementation of such an extended query evaluation procedure in a Prolog system can be implemented by a preprocessor for executing range restricted programs and requires no modification to the interpreter/compiler of an existing Prolog system. We compare this proposed extended query evaluation procedure with the extended program proposed by Lloyd and Topor, and the negation constructs in NU-Prolog. The use of the “not” predicate for integrity constraint checking in deductive databases is also presented.     

Efficient reordering of Prolog programs

Prolog programs are often inefficient: execution corresponds to a depth-first traversal of an AND/OR graph; traversing subgraphs in another order can be less expensive. It is shown how the reordering of clauses within Prolog predicates, and especially of goals within clauses, can prevent unnecessary search. The characterization and detection of restrictions on reordering is discussed. A system of calling modes for Prolog, geared to reordering, is proposed, and ways to infer them automatically are discussed. The information needed for safe reordering is summarized, and which types can be inferred automatically and which must be provided by the user are considered. An improved method for determining a good order for the goals of Prolog clauses is presented and used as the basis for a reordering system     

专家系统外壳ESTA的汉化研究及应用

Visual Prolog是国际上已经广泛流行的功能强大的通用智能化集成开发环境，ESTA（Expert System Shell for Text Animation）V4．5是随Visual Prolog V5．2推出的商业专家系统外壳。文章概述了ESTA的功能特点以及ESTA的汉化研究，利用汉化的ESTA开发并应用于变压器等设备故障诊断专家系统（基于三比值法则）。