Data processing: artificial intelligence – Knowledge processing system – Creation or modification
Reexamination Certificate
1997-09-19
2002-07-23
Trammell, James P. (Department: 2161)
Data processing: artificial intelligence
Knowledge processing system
Creation or modification
Reexamination Certificate
active
06424962
ABSTRACT:
BACKGROUND OF THE INVENTION
The invention relates to a method of automated proving for unrestricted first-order logic to test the satisfiability of clause sets describing an industrial system, the resulting automated proving tool and industrial system, and the information carrier incorporating a program carrying out the method.
FIELD OF THE INVENTION
Automated proving is concerned with the fundamental task of establishing the satisfiability or unsatisfiability of formula sets including cl use sets. A computational method dedicated to this task is called a proof method. Automated proving is involved in various logical computations which will be here covered by the global notion of automated reasoning: e.g. computation of counter-models of formula sets, automated theorem proving, computation of maximal satisfiable subsets of unsatisfiable sets of formulas, computation of minimal support of theorems, etc. The invention can be used by any industrial application where first-order logic automated reasoning can be explicitely or implicitely involved.
First-order logic has become of industrial interest through a restricted sublogic known as Horn clause logic. Horn clause formalism is used by logic programming languages like PROLOG both as a declarative and imperative language. The wide variety of applications which can be achieved with logic programs illustrates the versatility of Horn clause logic in expressing various problems (for example, see: “Artificial Intelligence through PROLOG”, Prentice Hall 1988, Rowe, N. C.). But in many cases the expressive power of Horn clause logic is not sufficient: unrestricted first order logic, and even higher-order logic, is needed. How to use unrestricted first-order logic in expressing problems or in describing digital circuits, computer programs, complex systems, etc, and how first-order logic automated reasoning allows computers to solve such problems is explained in many classical textbooks (for example, see: “Automated Reasoning”, Prentice Hall,1984, Wos, L. et al.).
Thus, beyond those related to Horn clause logic programming, there is a wide range of industrial applications where, explicitely or implicitely, first-order logic automated reasoning can be involved and the invention used, among which can be mentioned, for example:
General purpose automated reasoning systems: general purpose automated reasoning systems can be sold or distributed as stand-alone products (software products or dedicated machines) and/or within packages. They can be used to train or help mathematicians, logicians, computer scientists and any kind of end-users in checking and/or proving the validity and/or the satisfiability and/or the unsatisfiability of all kinds of statements which can be expressed in the forms accepted by the end-user interfaces and which can be translated in logic, this including among others various logical formalisms, pseudo-natural languages, graphic inputs, and any kind of dialog based interactions with users. General purpose automated reasoning systems may also provide more sophisticated functionalities, based on the computation of maximal satisfiable subsets of unsatisfiable sets of statements and/or the computation of minimal unsatisfiable subsets of given sets of statements. General purpose automated reasoning systems may also be used by other devices (softwares or hardwares) through various specific communication channels.
Truth maintenance systems: truth maintenance systems can be sold and/or distributed as stand-alone products or within artificial intelligence packages. They are oriented toward automatic verification of the satisfiability of sets of statements expressing various kinds of knowledge or specifications. They may also provide help for management of unsatisfiable sets of statements through computation of maximal satisfiable subsets. They may also provide tools to analyze logical dependencies between formulas and help minimize logical knowledge bases through computation of minimal unsatisfiable subsets.
Building and/or exploitation environments for knowledge based systems: they may incorporate more or less implicitly truth maintenance functionalities, and may also use automated proving to answer queries and draw conclusions from knowledge bases in exploitation mode.
Database management and exploitation systems: as environments for knowledge based systems, they may incorporate more or less implicitly truth maintenance functionalities in order to verify database conceptual schemas, and may also, in exploitation mode, use automated proving to answer queries about deductive databases.
Domain-oriented specific applications using implicitly or explicitly first-order logic automated reasoning, like, for example, fault-finding, diagnosis, maintenance, reliability analysis, prevision systems, etc, in various domains like, for example, technical, medical, financial, etc.
Methodological tools for the conception of information systems: conceptual schemas of information systems for enterprises and administrations of various scales can be translated into logic, and then formally checked with automated reasoning.
Software libraries (sources and/or object codes) or hardware co-processors which can be sold or distributed as stand-alone products or in packages, providing routines related to automated reasoning.
Formal verification and symbolic simulation of the specifications of dynamical devices or systems. When parts or totality of the specifications, at some level of discrete abstraction for continuous physical systems, can be expressed or translated in logic, various verifications of properties fulfillment can be performed by automated reasoning. In case of violation of some required properties, truth maintenance functionalities may be used to restore correctness. Automated reasoning may also be used to simulate in more or less instantiated context the behavior of the specified device or system. In this class of applications there are, for example:
formal verification and symbolic simulation of the specifications of various finite state machines: for example digital circuits, man/machine interfaces, etc.
formal verification and symbolic simulation of program specifications.
formal verification and symbolic simulation of the specifications of concurrent systems.
formal verification and symbolic simulation of the specifications of communication protocols.
formal verification and symbolic simulation of the specifications of complex systems, e.g. nuclear reactors, emergency plans, etc.
etc.
Formal verification, formal comparison to specifications and symbolic simulation of the description of real devices or systems. As with formal verification of specifications, except that there it is some logical description of real devices or systems which is of concern. Moreover, if specifications are available, the conformity of a real: system to its specifications can be checked by automated reasoning. In this class of applications there are, for example:
formal verification and symbolic simulation of various finite state machines: for example digital circuits, man/machine interfaces, etc.
formal verification and symbolic simulation of programs.
formal verification and symbolic simulation of concurrent systems.
formal verification and symbolic simulation of communication protocols.
formal verification and symbolic simulation of complex systems, e.g. nuclear reactors, emergency plans, etc.
etc.
Security analysis of programs, information and decision flowcharts.
BACKGROUND OF THE INVENTION
Currently available proof methods for first-order logic have a common drawback. They cannot provide simultaneously a level of performance and a degree of robustness sufficient to fulfill industrial needs.
Currently available proof methods rely on some common basic principles which give them a great propensity to waste time in performing redundant operations, except when by chance they quickly find a proof. As a consequence they have a great lack of robustness: robustness means here completeness and soundness plus regularity of performance on problems of similar complex
Bull S.A.
Greene Daniel L.
Kondracki Edward J.
Miles & Stockbridge P.C.
Trammell James P.
LandOfFree
Method of automated proving for unrestricted first-order logic does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method of automated proving for unrestricted first-order logic, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of automated proving for unrestricted first-order logic will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2838389