Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!cs.utexas.edu!uunet!mcvax!unido!uklirb!shell
From: u-dmfloy@ug.utah.edu (Daniel M Floyd)
Newsgroups: comp.ai.shells
Subject: Re: Expert System Complexity
Message-ID: <4663@uklirb.UUCP>
Date: 24 Apr 89 18:55:17 GMT
References: <4638@uklirb.UUCP>
Sender: shell@uklirb.UUCP
Organization: University of Utah CS Dept
Lines: 60
Approved: shell@uklirb.uucp

In article <4638@uklirb.UUCP> rehbold@uklirb (Robert Rehbold AG Richter) writes:
>I would like to start a discussion on what YOU think a "good" measure for
>expert system complexity.


	I think complexity could be measured by the number and type
of operations to be performed and whether or not parts are free or bound.
I don't know about what the trade off would be. For example,
Something with a (or this that) would rank lower than a (and this that)
because in the first case the rule is less restrictive than the second,
unless we start to deal with unbound conditions. (or this that) would
be *more* restrictive than an (and this _unboundThat) because here
the second case clearly could fire on several cases. It is hard to
say if it *will* match more, but I think the complexity is higher for the
bound case. I think that a (not _unboundThis) is more restrictive than
a (_unboundThis) because it limits the number of choices severely in the
first case while providing many choices in the second. "If and only if"
consturcts obviously would be more restrictive than simple "if".

	Like I said I don't know about the trade off - I'm refering
to combinations. I think it would be some sort of inversion or square maybe
for the nots, multiply for ands, and addition for ors, while treating
unbounds as ors. So, to give some 'value' to it, supose we have (done
in FROLIC a prolog like syntax):

(*- (exist a b)) ;This trivial data base is here just to get the idea.
(*- (exist c d)) ;It has nothing to do with complexity ... yet.

(?- (exist a b) (exist x y))
 ; Complexity = 
 ; (exist a b) = 3 
 ; (exist x y) = 3
 ; total       = 3 * 3 = 9

(?- (or (exist a b) (exist x y))) ;I think I goofed on syntax, but you get the idea.

 ; Complexity = 3 + 3 = 6

(?- (exist a b) (not (exist x y))) ;Syntax?

 ; Complexity = 3 * (square 3) = 27

(?- (exist a _b)) ;Complexity = 2

(?- (exist a b) (not (exist x _unbound))) ;Syntax?

 ; Complexity = 3 * (square 2) = 12


	We could also throw in a factor for each predicate so that
the more facts there are to match a predicate, the less complex the
predicate itself is deemed. Thus exist would get maybe a factor
of -2 since it has 2 facts while (a-no-fact-predicate) might get 0
since it has no facts to work with. Ops5 rules or any other
system would have similar ranking system.

	There's my half-baked 2 cents worth.

Dan Floyd
8<D=