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


Consumers The consumers C of a role r in an inference structure I, denoted
by C (r), are the inferences in I that have the role as an input.
Initial roles The initial roles of an inference structure I are the input roles
that are not produced by any inference step in I. We will use the notation [left arrow R]s to denote the set of input roles of the inference step s. When no indices are given, refers to the set of input roles of the whole inference structure.
Terminal roles The terminal roles of an inference structure I are the output
roles that are not consumed by any inference step in I. We will use the notation [left arrow R]s to denote the set of output roles of the inference step s.
Substitution to a knowledge role A substitution of a value a:type (where a is a
ground term) to a knowledge role [nu]:type is denoted by [sigma] = {[nu]/a}.
The instance of an inference step s obtained by carrying out substitution [sigma] is
denoted by s[sigma]. For multiple substitution, [sigma] is of the form [sigma] = {([nu]1/a1), ..., ([nu]n/an)}. The instance of an inference structure I obtained by carrying out substitution [sigma] to all its knowledge roles is denoted by I[sigma]. We use the notation [sigma]:type([left arrow R]), to denote that [sigma] is a substitution for a set of variables of exactly the types of the initial roles. In this case I[sigma] denotes an instance of the inference structure I obtained by carrying out the substitution [sigma], i.e., substitutions of all its input roles. We use the notation s[sigma], where [sigma]:type([left arrow R]s), to denote an instance of the inference step s obtained by substitution of its input roles. The same can be applied for terminal, internal, and external roles. When the type is not given, [sigma] is a substitution for all knowledge roles in the inference step or inference structure.
Sequence of substitutions The sequence of two substitutions
[sigma] = {([nu]1/a1), ..., ([nu]n/an)} and [nu] = {w;(w1/b1), ..., (wm/bm)} is denoted by [sigma]|-[nu] = {([nu]1/a1), ..., ([nu]n/an), (w1/b1), ..., (wm/bm)}.
The sequence operator has precedence over the application of the substitution to
an inference step or structure. When two substitutions substitute different values to the same variable, the right-most substitution has precedence (i.e., overwrites the left-most substitution for that variable). Example: consider the following inference step s(x1,x2;y), and two substitutions, [sigma]:type([left arrow R]s) and [nu]:type([left arrow R]s), where [sigma] = {(x1/5), (x2/6)} and [nu] = {(y/5)}, [sigma]|-[nu] = {(x1/5), (x2/6), (y/5)}. s[sigma]|-[nu] denotes an instance of s obtained by carrying out the substitution [sigma]|-[nu].
Satisfying an inference structure Let [sigma] be a substitution for all knowledge
roles occurring in an inference structure I, and DEF the definitions of all inference steps occurring in I. [sigma] satisfies I if and only if DEF | = I[sigma]. To avoid writing DEF repetitively and to improve the readability, we will write sat(I[sigma]) to denote that the inference structure I is satisfied by a substitution [sigma], where [sigma] corresponds to a valid execution of I. A valid execution of s means that the particular instance of s solves the problem-solving step for which it was designed. In the previous example, s[sigma]|[nu] is a valid instance of s if, for example, the inference step performs the minimum operation on its input knowledge roles. The same can be applied to inference structures. We use the notation sat(s[sigma]) to denote the satisfaction of the inference step s.

2.2.1. Subsumption

In hybrid systems, inheritance triggers subsumption among the objects and will lead to other types of anomalies unique to hybrid systems. A taxonomy of anomalies that can occur in such systems has been proposed by Lee and O'Keefe (1993):

  • Subsumed rules: Subsumed rules arise due to the subsumption relationship between literals used in the rules.
  • Redundancy: Redundancy arises as a direct consequence of subsumed rules.
  • Semantic conflict: Semantic conflict occurs when any pair of rules that have the same conditions lead to semantically different actions, among which there exists a partial or complete subsumption relationship.
  • Structural conflict: Structural conflict is identified by subsumption relationships in the condition and action parts of the rules.
  • Unnecessary conditions: In hybrid systems, unnecessary conditions can occur when an action in a rule is propagated to another rule as a condition and results in at least one subsumption relationship between a pair of literals in the condition clause.
  • Unreachable goals: Unreachable goals may arise due to mutual exclusivity among the objects used in the condition of the same rule.
  • Circular rules: The definition of circular rules has been extended for hybrid systems.

Instead of addressing directly the different types of anomalies due to subsumption mentioned above, we define different types of subsumption, and identify the type of anomaly that may be caused by that specific type of subsumption. This approach abstracts from implementational details, by addressing these issues on a conceptual level. For each type of subsumption, we provide a counterpart example, where an object hierarchy of two levels is assumed: S = a1’ [union] a2’ [union] ... [union] an’ being the first level and every ai1’ = {ai1, ai2, ..., aij} being the second level, where the elements in the set are subclasses of ai’.

A classification of the subsumption relation is given in Figure 2.

The explicit subsumption is the type of subsumption that has been considered in the traditional V&V activities in rule-bases. In rule base systems, subsumption occurs in the case that the more general rule can always be fired whenever the restrictive rule is fired. For example, whenever rule (1) succeeds, rule (2) will also succeed. Therefore, in what follows, rule (1) is subsumed by rule (2):

p(x) [wedge] q(x) —> r(x) (1)
p(x) —> r(x) (2)


FIGURE 2 A classification of the subsumption relation.


FIGURE 3 Partial (A) and complete (B) subsumption.

This kind of subsumption can be detected by comparing whether or not one rule has additional conditional statements to the other rule when the two rules have the same conclusion. However, such structural checking cannot cover the semantics of relationships in the rules of hybrid systems, which may include object hierarchies.

In order to cope with this problem, we introduce the notion of implicit subsumption. This type of subsumption1 takes into consideration the semantic relationships that exists between the objects on which the rules operate.


1We talk about subsumption between inference steps and subtyping between knowledge roles. In fact, subsumption between inference steps is caused by subtyping relationships between knowledge roles.

Implicit subsumption Let [sigma] = {([nu]1/a1), ..., ([nu]n/an)} and [sigma]’ = {([nu]1’/a1’), ..., ([nu]m’/am’)} where n [less than or equal to] m. [sigma] is subsumed by [sigma]’, written as [sigma] [inverted y] [sigma]’, iff

where ai , aj’ may be sets of values.

We distinguish two types of implicit subsumption, depending on the relationship between knowledge roles: partial and complete subsumption. An example of partial subsumption is given in Figure 3A, where the graphical notation is equivalent to s(x,y;z) [inverted wedge] s’(x’;z), using the notation provided in the previous section. An example of complete subsumption is given in Figure 3B, equivalent with s(x,y;z) [inverted wedge] s’(x’,y’;z).

In Figure 3, s is subsumed by s’ as for any value of x, where x is a subtype of x’,s’ computes the same value for z as s does, regardless of y. We will use to denote partial or complete subsumption, and [inverted y]c to denote complete subsumption.

In the following, we define the different types of subsumption. For each type, a brief analogy with the counterpart in rule bases is also given.


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.