Brought to you by EarthWeb
IT Library Logo

Click Here!
Click Here!

Search the site:
 
EXPERT SEARCH -----
Programming Languages
Databases
Security
Web Services
Network Services
Middleware
Components
Operating Systems
User Interfaces
Groupware & Collaboration
Content Management
Productivity Applications
Hardware
Fun & Games

EarthWeb Direct EarthWeb Direct Fatbrain Auctions Support Source Answers

EarthWeb sites
Crossnodes
Datamation
Developer.com
DICE
EarthWeb.com
EarthWeb Direct
ERP Hub
Gamelan
GoCertify.com
HTMLGoodies
Intranet Journal
IT Knowledge
IT Library
JavaGoodies
JARS
JavaScripts.com
open source IT
RoadCoders
Y2K Info

Previous Table of Contents Next


4.2. LOGIC PROGRAMMING SYSTEMS AND THEOREM PROVERS

Logic has also been used as the basis for the development of programming languages. A programming language based in logic typically restricts the logic for computational efficiency, avoiding the full treatment of features like negation, disjunction, and equality. The most popular family of logic programming languages use backward-chaining, depth-first search, backtracking, resolution inference, and add nonlogical features for input-output. The best-known example of logic programming languages is PROLOG. The relationship between logic and algorithm has been popularized by Robert Kowalski in his equation:

Algorithm = Logic + Control

which suggests that an algorithm results from appropriately augmenting a knowledge base of formulae with information to control the inference process that uses that knowledge (Kowalski). PROLOG has been widely used as a rapid prototyping language and in the implementation of many expert system applications in most domains.

Theorem provers use a proof procedure such as resolution, sequent, calculus, tableaux, mathematical induction, etc. to prove that a formula can be deduced from a knowledge base using some type of logic. Typically, they use backward-chaining reasoning, search control methods, and heuristics to prune the search space generated by the potential application of inference rules. OTTER and NQTHM are two of the best-known theorem provers. OTTER is based on resolution and NQTHM is based on mathematical induction. Both have been used extensibly in the construction of intelligent development environments for the design of software and hardware systems.

4.3. SEMANTIC NETWORKS AND FRAME SYSTEMS

Semantic networks and frame systems use a network structure to represent knowledge and reasoning techniques. The nodes of the graph represent objects that may have a hierarchical structure, and the arcs represent binary relations between the nodes. Thus, conceptually both systems use the same representation formalism, although the implementation is different. In a frame system, the arcs are regarded as slots of one frame that are filled by another frame, whereas in a semantic network the arcs are regarded as mathematical relations. Frame representations are represented by nested boxes and semantic networks are represented by graphs. Semantic networks emerged right after Peano formalized the notation of FOL around 1886 and were first proposed by Charles Peirce. Frame systems were proposed by Marvin Minsky who used them as a knowledge representation formalism in the area of computer vision (Minsky). Now, we know that any semantic network or frame representation can be translated into a logic representation, where the important aspects are the semantics and the proof procedures defined, rather that the notation features of the formalism. Both formalisms define nonmonotonic inference to reason about properties inherited by a class of objects to subclasses and objects in the hierarchy. Semantic networks and frame systems tools are also widely used in many expert and intelligent systems. CYCL, which is the representation language used in the CYC project, represents most of the features of a frame-based system (Lenat).

Description logics have evolved from semantic networks to facilitate the definition of categories of objects; thus, they are a type of higher-order logic. The ability to describe and reason about categories increases the expressibility of the logic. The main inference rules are subsumption to determine category membership and classification to determine object membership. The problem with this formalism is that inference can become intractable and incomplete, so the language is often restricted, and operations like negation and disjunction are either not allowed or limited in their form. The CLASSIC system is an example of a language of description logics (Borgida). This formalism has had application in domains like finance, information systems, and system interfaces.

Truth maintenance systems define mechanisms for the update of the knowledge base in nonmonotonic reasoning, where previously derived knowledge may have to be retracted in the presence of new knowledge. A truth-maintenance system keeps track of dependencies among elements of a knowledge base to efficiently update the knowledge base and keep it consistent. Truth-maintenance operations easily become intractable and are difficult to implement in complex applications (Doyle).

4.4. CASE-BASED SYSTEMS

Deductive reasoning is a type of reasoning from first principles (axioms and inference rules). However, human experts often solve problems by recalling past experiences and situations where similar problems have been found and solved, remembering the result, and possibly, the reasoning used to obtain that result. The problem at hand is then solved by adapting past solutions to similar problems by a kind of analogical reasoning. The systems that adopt this paradigm are called case-based reasoning (Schank). The main problem here is the storage and retrieval of the relevant cases for the current case. Indexing techniques have been developed to establish navigation paths among cases by different attributes and classes of attributes. CBR tools exist (i.e., CBR Express) and are being used to develop expert systems in diverse areas of application.

4.5. META-LEVEL REASONING

Meta-level reasoning is concerned with inferences using meta-knowledge, which is the knowledge about the knowledge owned by an intelligent system. A type of meta-knowledge is control knowledge, defined as rules that specify which rules to fire in a given situation or the order in which to solve subgoals. Control knowledge can also be represented as frames as implemented in the CYC project. Another type of meta-knowledge is the knowledge used to disambiguate sentences in natural language processing as implemented in CYC as well. CYC maintains two levels of representation: the epistemological level and the heuristic level. The former represents knowledge in a logic language, which is the language known to the user; the latter represents the same knowledge in computational structures for efficient processing. This distinction represents a way of combining the elegance of logic with the computational efficiency of frames (Lenat). Meta-level inference started with the work of Hayes in 1973 (Hayes) and continued with the work of several researchers who developed systems, including AMORD (deKleer), TEIRESIAS (Davis), MRS (Genesereth), METALOG (Dincbas), PRESS (Silver), and CLAM (Bundy).


Previous Table of Contents Next

footer nav
Use of this site is subject certain Terms & Conditions.
Copyright (c) 1996-1999 EarthWeb, Inc.. All rights reserved. Reproduction in whole or in part in any form or medium without express written permission of EarthWeb is prohibited. Please read our privacy policy for details.