JOURNAL OF SYSTEMS SCIENCE AND SYSTEMS ENGINEERING / Vol. 12, No. 2, June, 2003

145

A Formal Systems Approach to Solver Design

that for any solvable c∈C a∈backtrack(c) iff a∈genA(c) and δ(c,a) is a solvable state. The goal g will be used to select an action among genA(c) for a state c. Then, it need not be compatible with the order of C. However, if it is compatible, it will be shown to derive stronger results. We use the following compatibility condition. Definition 8 Compatibility condition for g A goal is said to satisfy a compatibility condition iff it satisfies the following relation: For c,c'∈∪Cp g(c) ≤g(c')↔c≤c'. Notice that Y=C and since ≤ on C is a linear order, y≤y' →g(y) ≤g(y') implies y≤y' ↔g(y) ≤g(y'). Definition 9 Strategy of the hill climbing method with push down stack:σpd:∪Cp→A Let σpd:∪Cp→A be σpd(c)=a* where a* ∈backtrack(c) and satisfies max{g(δ(c,a))|a∈backtrack(c)}=g(δ(c,a*)). Then, σpd will be called strategy of the hill climbing method with push down stack. The goal seeker of this paper is characterized by σpd. It should be noticed that σpd can be defined even if g is not compatible. σpd is not a simple feedback law because it requires a backtrack operation to assure δ(c, σpd(c)) is a solvable state. The following concept is already introduced informally. Definition 10 Dynamical mapping: πσ:C→C Let σ:C→A be a strategy. Then, let πσ:C→C be πσ(c)=δ(c,σ(c)). πσ is called dynamical mapping of σ. Definition 11 Loop free strategy

146

A strategy σ:C→A is called loop free if it satisfies (∀p,q)(p≠q →πσp(c0)≠ πσq(c0)). The following is an obvious but a fundamental fact for problem solving. Theorem 1 Suppose C is finite and the initial state is solvable. Then, if a strategy σ is loop free, there is p such that πσp(c0)∈Cf or it yields a solution. Proof. Let Cp={c0, πσ(c0),…, πσp(c0)}. Since σ is loop free, C1⊊C2⊊…⊊Cp. Since C is finite, Cp∩Cf≠φ for some p. Q.E.D. The following is also intuitively clear. Proposition 1 Let c∈Cp be arbitrary. Then (∀α)(∃q)(α∈legalAs(c) & δ(c,α)=c'→c'∈Cq). Proof. We use the mathematical induction. (i) Suppose α=a∈legalAs(c). Then, a∈genA(c) and constraint(δ(c,a))=true. Let c'=δ(c,a). Due to the definition of Cp+1 c'∈ Cp+1 ∨ c'∈∪{Cr| r≤p}. If c'∉Cp+1, then (∃r)(c'∈Cr). (ii) Suppose if length(α) ≤ l, δ(c,α)∈Cq for some q. Let β=αa and length(β)=l+1 where a∈genA(δ(c,α)) is arbitrary. The induction hypothesis implies δ(c,α)∈Cq for some q. Then, the argument (i) implies that δ(δ(c,α),a)∈Cq+1 or δ(δ(c,α),a)∈Cr for some r. Q.E.D. The following is also a fundamental fact for the methodology of this paper. Proposition 2 Let α∈legalAs(c0) be arbitrary. Let c'=δ(c0, α). Then, (∃α'∈legalAs(c0))(α'=a1...ak & δ(c0,a1,..,ai)∈Ci for each i & δ(c0,α')=c'). Proof. Because of Prop. 1 there is k such that δ(c0,α)=c'∈Ck. Since c'∈ Ck={c'|a∈genA(c) &

JOURNAL OF SYSTEMS SCIENCE AND SYSTEMS ENGINEERING / Vol. 12, No. 2, June, 2003

TAKAHARA, LIU and YANO

δ(c,a)=c' & c∈Ck-1 & constraint(c')=true}}∪{Cr| r≤k-1}, c'=δ(ck-1,ak) & ck-1∈Ck-1 & ak∈genA(ck-1) & constraint(c')=true. Since ck-1∈Ck-1, there exist ck-2 and ak-1 such that ck-1=δ(ck-2,ak-1) & ck-2∈Ck-2 & ak-1∈genA(ck-2) & constraint(ck-1)=true. In this way we can find a1,a2,...,ak, c1,...,ck-1 such that δ(c0,a1)=c1∈C1 & a1∈genA(c0) & constraint(c1)=true, δ(c1,a2)=c2∈C2 & a2∈genA(c1) & constraint(c2)=true,

M

δ(ck-1,ak)=c'∈Ck & ak∈genA(ck-1) & constraint(c')=true. Consequently, α'=a1...ak∈legalAs(c0), δ(c0,a1...ai)∈Ci and δ(c0,α')=c'. Q.E.D. Then, Theorem 2 There is a solution path iff an efficient solution path exists. Proof. The if part is obvious. The only if part comes from Prop. 2 where c'∈Cf. Q.E.D. We will characterize an efficient solution path. The following should be obvious. Corollary 1 Suppose α =a1a2...ap ∈ legalAs(c0) is a solution path. Suppose α satisfies the following relations. δ(c0,a1)=c1∉C0, δ(c1,a2)=c2∉C0∪C1,

M

δ(cp-1,ap)=cp ∉∪{Ck|k
order of C) on the way to a target state. The following should be also obvious. Corollary 2 Suppose α =a1a2...ap ∈ legalAs(c0) is a solution path. Suppose α satisfies the following relations. a1∈genA*(c0), a2∈genA*(c1) where δ(c0,a1)=c1, a3∈genA*(c2) where δ(c1,a2)=c2,

M

ap∈genA*(cp-1) where δ(cp-2,ap-1)=cp-1. Then, α is an efficient solution path. Q.E.D. When g is compatible, we have strong results for σpd,. Proposition 3 Let c∈Cp is solvable. Suppose g is compatible. Let a*∈σpd(c) where σpd is a strategy of the hill climbing method with a PD stack. Then, δ(c,a*)∈ Cp+1. Proof. Since c is a solvable state, Prop.2 asserts that there is α=a1…ak∈legalAs(c) such that δ(c,a1)=c1∈Cp+1, δ(c1,a2)=c2∈Cp+2,

M

δ(ck-1,ak)=ck∈Cf. Since a1∈genA(c) and δ(c,a1) is a solvable state, c<δ(c,a1) implies g(c)
JOURNAL OF SYSTEMS SCIENCE AND SYSTEMS ENGINEERING / Vol. 12, No. 2, June, 2003

147

A Formal Systems Approach to Solver Design

Finally,

it may indicate that the goal seeker has reached a

Theorem 3 σpd of the hill climbing method

final state. (Refer to the definition of Cf in Chap.

with a push down stack always yields an

5.) In either case the operation of the goal seeker

efficient solution path if the initial state is a

must finish. If the trial is successful, the goal

solvable state and g is compatible.

seeker gets (c,As,H), current state, set of

In practices there are two ways to derive an

available actions ⊂ genA(c) and history of the

efficient solution path. The first is to use Cor. 1.

visited states as the top information. It then

Cor. 1 says that an efficient solution path is

selects (a*,RA) where a*=σ(c) and RA=As-{a*}.

produced if a next state ci is found outside of

a* is assumed to satisfy the relation

∪{Cp|p
max{g(δ(c,a))|a∈As}=g(δ(c,a*)).

memorize ∪{Cp|p
δ(c,a*) must not be equal to an element of H

of memory, it may yield difficulty with respect

(Refer to Th. 1). If c is a dead lock state, a*=[] is

to computation and memory. Then, if we use a

assumed. In this case the goal seeker must do the

heuristic that the history H of the visited states

back track operation, that is, pops up the next

may cover an essential part of ∪{Cp|p
information.

used, H may be substituted for ∪{Cp|p
Notice that it can be proved by the

general, this heuristics may be helpful because H

mathematical induction that if a0*a1*...ap* is a

must be used in order to make a strategy loop

solution generated by the extSLV, the following

free.

property holds:

The second is to use Th. 3. In that case the goal g is required to be compatible. Although the

max{g(δ(ci,a))|a∈backtrack(ci)}=g(δ(ci,ai*)) where ci+1=δ(ci,ai*).

compatibility condition might be considered to

If a* is a regular action (a*≠[]), the goal

hold only in an exceptional case, it is not

seeker applies a* to the process δ to get the next

necessarily true. If a target problem belongs to

state cc=δ(c,a*). It generates the set of available

the class of implicit solving action and a:Y→Y

activities As2 for the next state cc. If cc∈Cf or

is selected as an action to improve an output y

st(cc)=true

and if the goal g is defined to reflect the degree

process must finish. If cc∉Cf, the goal seeker

of improvement, the compatibility condition

saves (push down) two information, (c,RA,H)

holds.

and (cc,As2,H2) where H2=H⋅c, i.e., the current

The

data

mining

system

problem

corresponds to this case. Figure 7 shows the total process of a unified goal seeker based on Cor. 1 and Th. 3. Every information to yield an action σ(c) is stored in a push down stack. The goal seeker,

(stopping

condition),

the

total

state c is appended to H. The former information (c,RA,H) will be used when the goal seeker does back track to the state c. The latter information is used at the next state cc. Then, it goes to the pop up stage.

first, tries to pop up the top information. If the

The total system, extSLV, which consists of

trial fails, in general it indicates failure of the

the goal seeker and the process δ, is formalized

goal seeker. However, in the case of open target,

as a generator:

148

JOURNAL OF SYSTEMS SCIENCE AND SYSTEMS ENGINEERING / Vol. 12, No. 2, June, 2003

TAKAHARA, LIU and YANO

extSLV

yes stack = [ ]?

end/fail

no (y, As, H) ← popup(stack)

(a * , RA) ← µ(c, As, H) yes

goal: g(c)

a* = [ ]?

(back track)

no cc← δ(c, a*)

As2 ← genA(cc), H2 ←H·c

st(cc) = true ?

yes

no pushdown((c, RA, H)(cc, As2, H2))

end

Figure 7 extSLV by unified general goal seeker based on Cor. 1 and Th. 3 extSLV= where Stack is the state set and (c0,genA(c0),[],[]) is an initial state. Stack, solProc:Stack→Stack and st:C→{true,false} are defined in the following way. Let Γ=C×℘(A)×H×Sol; stack element, H=C*; history of states, Sol=S*; history of actions,

Stack=Γ*, where Sol is used as an auxiliary variable for error checking. Then, µ:Γ→A×℘(A) is (a*,As-{a*}) if max{goal(δ(c,a))| µ (c,As,ϕ,α) = a ∈ As & constraint(δ(c,a)) = true}= goal(δ(c,a*)) ([],[]) o.w. In the definition of µ the condition a*∈backtrack(c) is not required because the

JOURNAL OF SYSTEMS SCIENCE AND SYSTEMS ENGINEERING / Vol. 12, No. 2, June, 2003

149

A Formal Systems Approach to Solver Design

condition “δ(c,a*) is a solvable state” is supported by the back tracking as mentioned above. solProc:Stack→Stack is γ*γn'γn+1 solProc(γ*γn)= if µ (γn)=(a*, RA) and a*≠[] γ* o.w. where γn=(c,As, ϕ,α), γn'=(c,As-{a*}, ϕ,α), γn+1=(δ(c,a*),genA(δ(c,a*)), ϕ⋅c,α⋅a*). st:C→{true,false} is st(c)=true↔c∈Cf. The extSLV is actually a push down automaton without input. ID code D1 D2 D3 D4 D5 D6 D7 D8 D9 D10 D11 D12 D13 D14 D15 D16 D17 D18 D19 D20 D21 D22 D23 D24

lenses none, soft, none, hard, none, soft, none, hard, none, soft, none, hard, none, soft, none, none, none, none, none, hard, none, soft, none, none,

age young, young, young, young, young, young, young, young, pre_presbyopic, pre_presbyopic, pre_presbyopic, pre_presbyopic, pre_presbyopic, pre_presbyopic, pre_presbyopic, pre_presbyopic, presbyopic, presbyopic, presbyopic, presbyopic, presbyopic, presbyopic, presbyopic, presbyopic,

A part of the corresponding output is as follows: If age=pre_presbyopic then lenses=none with confidence 6.2500e-01 and support

150

5. Example by Data Mining System Problem The general design procedure mentioned in Chap. 4 will be illustrated by using the data mining system problem. Although a data mining system problem is very important in practice, it is a rather simple problem in theory as will be shown below. The example is, however, selected in order to emphasize practicality of the method of this paper. (i) Input-Output Block Diagram Figure 5 shows an input output block diagram of the data mining system problem. In particular, the following data set will be used as an example (Witten and Frank 1999). prescription myope, myope, myope, myope, hypermetrope, hypermetrope, hypermetrope, hypermetrope, myope, myope, myope, myope, hypermetrope, hypermetrope, hypermetrope, hypermetrope, myope, myope, myope, myope, hypermetrope, hypermetrope, hypermetrope, hypermetrope,

astigmatism no, no, yes, yes, no, no, yes, yes, no, no, yes, yes, no, no, yes, yes, no, no, yes, yes, no, no, yes, yes,

tear reduced, normal, reduced, normal, reduced, normal, reduced, normal, reduced, normal, reduced, normal, reduced, normal, reduced, normal, reduced, normal, reduced, normal, reduced, normal, reduced, normal

5.000000 If age=presbyopic then lenses=none with confidence 7.5000e-01 and support 6.000000 If prescription=hypermetrope then

JOURNAL OF SYSTEMS SCIENCE AND SYSTEMS ENGINEERING / Vol. 12, No. 2, June, 2003

TAKAHARA, LIU and YANO

lenses=none with confidence 6.6667e-01 and support 8.00000 If astigmatism=yes then lenses=none with confidence 6.6667e-01 and support 8.00000 If tear=reduced then lenses=none with confidence 1.0000e+00 and support 12.00000 If age=young and tear=reduced then lenses=none with confidence 1.0000e+00 and support 4.000000 If age=pre_presbyopic and prescription =hypermetrope then lenses=none with

input:

confidence 7.5000e-01 and support 3.000000 If age=pre_presbyopic and astigmatism=yes then lenses=none with confidence 7.5000e-01 and support 3.000000 The confidence level=0.6 and the support level=2 are used. (ii) Input-Output Specification in the Set Theory Figure 8 illustrates Stage 2 of the data mining system problem.

SLV for

output: y∈Y

data mining Figure 8 Input-output specification in the set theory of the data mining system problem The input is given by a structure V=∪VLst , and whose components are specified below. V+= V2∪…∪Vn. a. Let the attribute list of the given data be: c. Let ALst={ai|i ∈ Ia} (Ia={1,2,…,n}) X=℘(V1 ×…×Vn) (the power set of V1 where a1 is a conclusion or the output ×…×Vn) attribute and a2,…,an are input attributes. and D0 ∈ X: input data set of data mining. Ia is ordered with respect to the usual order. D0 is a given target data set to which data Let mining is applied. + Ia = Ia−{1} The output set Y is a class of sets of rules. Let a rule r be represented as and + + ALst ={ai|i ∈ Ia }. r ∈((ALst+×V)*×V1×Re×Int). b. Let If r=((a',v')…(a",v"),v1,r,n), it implies the Vi=dom (ai): domain of ai or value set of ai following rule: where if a'=v' and…and a"=v" then a1=v1 with i Vi={vij| j ∈ Iv }. confidence r and support n. Then, since y∈Y is a set of rules, Let VLst={V1,...,Vn}. y∈℘((ALst+×V)*×V1×Re×Int), Let or

JOURNAL OF SYSTEMS SCIENCE AND SYSTEMS ENGINEERING / Vol. 12, No. 2, June, 2003

151

A Formal Systems Approach to Solver Design

Y⊂℘((ALst+×V)*×V1×Re×Int). (iii) Process Specification as Automaton Although the input set A was defined as a subset of {a|a:Y→Y} or a∈A is a mapping, a will be represented as a parameter to specify a mapping from Y to Y. Let A=℘(ALst+), or a∈A is a subset of ALst+. In order to avoid confusion an element of A will be typically denoted by As∈A. The fact that As∈A is a set rather than a simple element makes a representation of the data mining system complicated although its structure is simple. If As∈A is applied to y∈Y, As creates new rules from y refining elements of y or the number of total rules increases. This is the desired improvement of the output. Roughly speaking, the rule creation is done as follows: Suppose a'∈As⊂ALst+ and r is a rule. a' is an attribute. Then, application of a' to r creates a new class of rules whose conditional parts are extended to include the attribute a'. In this creation stage the confident condition is ignored. Let us consider the following example: Let r be “If age=pre_presbyopic then lenses=none with support 5”. Notice that the confidence part of the rule is neglected. If a'=“prescription”, one of the created rules may be: “If age=pre_presbyopic and prescription=hypermetrope then lenses=none with support 3”. Since dom(prescription)={myope, hypermetrope}, two rules may be created from r (prescription=myope or prescription=hypermetrope ) if they satisfy the support level.

152

Let the new rule be denoted by (a',v')(r). In the above example v'= hypermetrope. Then, the class of rules created by As⊂ALst for each y is represented as follows: create(As,y)=∪{∪{{(a',v')(r)|v'∈dom(a')}|r ∈y}|a'∈As}. Then, As(y), the total rule set generated by As, is given by As(y)=y∪create(As,y). Let us represent the idea formally. Since a nested set definition is not implemented in the current extProlog, δ:C×A→C is given by the following three functions, δ1, δ2 and δ3: δ1:C×ALst+→℘(C), δ2:Rule×ALst+→℘(Rule), δ3:Rule×(ALst+×V)→Rule where Rule= ((ALst+×V)*×V1×Re×Int). Then, δ(y,As)=∪{δ1(y,a)|a∈As}∪y; δ1(y,a)=∪{δ2(r,a)|r∈y}; δ2(r,a)={r'|δ3(r,(a,v))=r' & v∈dom(a)}; ( α(a,v),v1, conf,n') δ3((α,v1,conf,n),(a,v))= if a∉dom(α) and n'≥supL Λ o.w. where As∈A, α∈(ALst+×V)*, dom(α)={a|(∃v)((a,v)∈α)} and n' is the number of entries in D0, which satisfy α, a=v and a1=v1. Notice that the confidence conf is dummy because the confidence condition is ignored at the rule creation stage. The confidence condition is taken care of by λ:C×A→Y. Let λ1:Rule→Rule be (α,v1,conf',n) λ1(α,v1,conf,n)= if conf'≥confL Λ o.w.

JOURNAL OF SYSTEMS SCIENCE AND SYSTEMS ENGINEERING / Vol. 12, No. 2, June, 2003

TAKAHARA, LIU and YANO

conf' is the real confidence value of the rule (α,v1). Then λ (c,As)={λ1(r)|r∈c}. genA is given as genA(c)={ALst+}. The above definition of genA comes from the fact that the data mining is an exceptional case where since As⊂As'→δ(y,As)⊂δ(y,As') for any y, an optimal solution of the hill climbing strategy with respect to the goal given below is explicitly known as {ALst+} from the beginning. constraint:C→{true,false} is given by constraint(y)=true iff no duplication in y & (∀r∈y)(no duplication in attr(r)) & (∀r∈y)(support(r)≥supL and confidence(r) ≥ confL) where support(α,v1,conf',n)=n and confidence(α,v1,conf',n)=conf'. The last constraints are included in δ3 and λ1. The initial state c0∈C is given by the most trivial situation; c0=φ; empty set. Finally, let target states Cf⊂C be specified as y∈Cf↔(a∈A)(δ(y,a) is undefined). In other words, the dead lock situation is a target state where the largest set of rules is created, which comes from the specification of genA. This is another peculiarity of the data mining system example. The process of the data mining system problem is given by an automaton . In the current formulation c≤c' iff |y|≤ |y'| . (iv) Dynamic Optimization Formulation Since a goal of the data mining system problem can be assumed to produce the

maximum set of rules, the goal g:C→Re is specified by the following: g(y)=|y|. Due to the definition of ≤ on C the following relation hold: c ≤ c'↔g(c)≤g(c'). That is, the goal satisfies the compatibility condition. (v) Generator Formulation The generator is independent of a problem.

6. Implementation An extSLV for the data mining system problem is obtained by implementing the formulation in Chap. 5 in extProlog. A detailed discussion about the extProlog is presented in Ref. (Takahara and Liu 1999). Appendix presents a complete list of an extSLV of the data mining system problem except the implementation of λ. The following comments may be helpful to understand the implementation. (i) Rule: The extProlog allows a frame representation of a data structure. A rule is represented by a frame where the real data set is stored in dlist instead of the support number, which makes processing of δ efficient. (ii) State: Since genA(c)={ALst+} is a singleton set, Cp={cp} is also a singleton set. cp is a set of rules whose conditional part has the length of p. That is, if r∈c1, r takes the form: if a'=v' then a1=v1 with confidence conf' and support n. Then, y or state c is layered as c=c0∪c1∪…∪ck and cp+1 is obtained by applying ALst+ to cp. In the implementation, then, the state is trivially represented by c=[k, k–1,…,0], where p

JOURNAL OF SYSTEMS SCIENCE AND SYSTEMS ENGINEERING / Vol. 12, No. 2, June, 2003

153

A Formal Systems Approach to Solver Design

corresponds to cp, and cp is by the predicate “state(p,[r1,…,rs])” where ri is the identifier of a rule in cp or the identifier of the frame of the rule. (iii) Goal Seeker: Figure 7 is faithfully implemented for the goal seeker except that the back track path is neglected because there is no back track due to the special form of genA. (iv) Relation: A relation is represented as a predicate or a set of facts. (v) Function: A function is represented as a relation. Although a conventional Prolog cannot admit a function, the extProlog allows a relation to be used as a function. The “function” declaration illustrated in Appendix specifies which predicates can be used as functions. For instance, the predicate “element” is declared as a function. Then, it can be used as a function although it is defined as a predicate. (vi) Set: A set is represented as a list. Only problem with the convention is that a list has an order among its elements although a set does not have. Then, the equality check between sets cannot be made simply. A program always sorts lists before making the equality check of sets. (vii) Generator: A generator, which is nothing but a function definition by the primitive recursion, is implemented simply by a recursive call. For instance, let , delta:C→C, be a generator whose stopping condition is st:C→{T,F}. Then, it is implemented as process(C,C2):delta(C,CC), if st(CC)=T then C2:=CC else process(CC,C2) end; (viii) Minimization: If the minimization is used,

154

it can be easily implemented in Prolog because a set is represented as a list, “ordered” set. For example, suppose f(X)=min{Y| h(X,Y)=T and Y∈Ys}. Then, f is given by the following program: f(X,Y):assign(regY,[]), sortmin(Ys,Ys0), assign(regZ,Ys0), repeat, regZ([Z|Zs]), if h(X,Z) then assign(regY,Z), Done:=1 else Done:=0 end, assign(regZ,Zs), Done=1 or Zs=[],!, regY(Y); (ix) Quantifier: A difficult problem of the implementation in the extProlog is how to handle a predicate with a quantifier. When a predicate has a quantifier (existential or universal), we have to scan the domain of a quantified variable. For instance, if X={x1, ...,xn}, (∀x)(P(x)) is examined by checking the formula P(x1)&...&P(xn). Similarly, (∃x)(P(x)) is checked by the formula P(x1)∨...∨P(xn). Then, since the checking is certainly time consuming, it requires some trick. The extProlog has special system defined predicates written in C to handle the case.

JOURNAL OF SYSTEMS SCIENCE AND SYSTEMS ENGINEERING / Vol. 12, No. 2, June, 2003

TAKAHARA, LIU and YANO

7. Concluding Remark This paper shows a formal systems theoretic approach to development of a solver for a problem solving type information system. The approach implies set theoretic modeling based on systems concepts and implementation in the extProlog. According to the approach problems are classified into the 8 cases. This paper deals with the least structured case. A solver is modeled as a goal seeking system. A hill climbing method with a push down stack is used for design of the strategy of the solver and is characterized by the concept of efficient solving path. The data mining system problem is used as an example. This research clearly shows at least three advantages of the formal system approach. (i) It has been said that the systems approach can reveal a structure of a target. In the current research that advantage can help us 1. To classify problems. 2. To decompose a problem structure into two parts, problem dependent part and problem independent part. Although the current problem classification is at a preliminary stage, it can still give us a clue how to handle a new problem. The decomposition can make a big contribution to rapid systems development. Since the problem independent part, i.e., goal seeker part, is the most difficult part, it is quite helpful that we do not have to design it but can use a standard one for it. (ii) It is obvious that the formal approach makes arguments operational. Discussions can be deepened and precise, which enables us to present results in the mathematical style

(definition-theorem-proof) and to find errors in implementation. (iii) Due to the narrow semantic gap between a set theoretic description and Prolog implementation the set theory oriented formal approach results in rapid systems development.

Appendix /*dataminingPD.p*/ frame(rule,[[alist,[]],[vlist,[]],[dlist,[]]]); element(Dlist,I,V,U,D):procC("getelement",[Dlist,I,V,U],[D]); q():function([ aLst, attrN, element, support, confidence, ]), /*data set*/ D0:=[ [none,young,myope,no,reduced], [soft,young,myope,no,normal], [none,young,myope,yes,reduced], [hard,young,myope,yes,normal], [none,young,hypermetrope,no,reduced], [soft,young,hypermetrope,no,normal], [none,young,hypermetrope,yes,reduced], [hard,young,hypermetrope,yes,normal], [none,pre_presbyopic,myope,no,reduced], [soft,pre_presbyopic,myope,no,normal], [none,pre_presbyopic,myope,yes,reduced], [hard,pre_presbyopic,myope,yes,normal], [none,pre_presbyopic,hypermetrope,no,reduced], [soft,pre_presbyopic,hypermetrope,no,normal], [none,pre_presbyopic,hypermetrope,yes,reduced], [none,pre_presbyopic,hypermetrope,yes,normal], [none,presbyopic,myope,no,reduced], [none,presbyopic,myope,no,normal], [none,presbyopic,myope,yes,reduced], [hard,presbyopic,myope,yes,normal], [none,presbyopic,hypermetrope,no,reduced], [soft,presbyopic,hypermetrope,no,normal], [none,presbyopic,hypermetrope,yes,reduced], [none,presbyopic,hypermetrope,yes,normal]], /*support level;confidence level*/ assign(supL,2), assign(confL,0.6),

JOURNAL OF SYSTEMS SCIENCE AND SYSTEMS ENGINEERING / Vol. 12, No. 2, June, 2003

155

A Formal Systems Approach to Solver Design

/*auxiliary relations*/ ALst:=[lenses,age,prescription,astigmatism,tear], assign(aLst,ALst), VLst:=procC("getcategory",[D0,ALst]), assign(vLst,VLst), Iap:=procC("createindex",[2,strlen(ALst)-1]), assign(iap,Iap), /*initial state*/ getID(ID), defFrame(rule,ID,[]), concat([rule,".",ID],Fr), Fr->dlist:=D0, C0:=[0], assert(state(0,[ID]):-!), /*initial statck valiue*/ genA(C0,As0), assign(regStack,[[C0,As0]]), /*initialize display of goal behavior*/ goal(C0,R), assign(regG,[R]), /*start solution*/ assign(regC,[]), goalseeker(CC), /*end of solution*/ project(CC,1,K), xwriteln(0,"end of goalseeker:final K=",K), Sts:=procC("createindex",[1,K]), /*output*/ assign(rNum,0), appendf("dmrules2","w",""), lambda(Sts); ?-q(); delta([K|Ks],As,C2):state(K,SL), //xwriteln(0,"sigma:state=",[K,SL]),stop, C:=[K|Ks], assign(regA,As), assign([state,K+1],[]), repeat, regA([X|Xs]), delta1(C,X,CC), assign(regA,Xs), Xs=[],!, state(K+1,SL2), if SL2=[] then C2:=[] else append([K+1],C,C2) end;

156

state

index

delta1([K|Ks],A,CC):state(K,FIndex), assign(regFI,FIndex), assign(regCC,[]), repeat, regFI([I|Is]), concat([rule,".",I],Fr), As:=Fr->alist, append(As,[A],As2), sortmin(As2,As20), if As<>[] then Min:=min(As) else Min:=100000 end, if Min>A then delta2([K|Ks],I,A,CC0), assign(regCC,CC0) else assign(regCC,[]) end, assign(regFI,Is), Is=[],!, regCC(CC), retract([regFI,regCC]); delta2([K|Ks],I,A,CC):dom(A,Vs), assign(regV,Vs), assign(regfin,0), repeat, regV([V|Vs2]), if delta3(I,[A,V],I2) then assign(regfin,1), state(K+1,L), if I2<>[] then append(L,[I2],L2) else L2:=L end, assign([state,K+1],L2) end, assign(regV,Vs2), Vs2=[],!, regfin(F), retract([regV,regfin]), if F=1 then C:=[K|Ks], append([K+1],C,CC) else CC:=[] end; delta3(I,[A,V],I2):/*get frame of I*/ concat([rule,".",I],Fr), As:=Fr->alist,

JOURNAL OF SYSTEMS SCIENCE AND SYSTEMS ENGINEERING / Vol. 12, No. 2, June, 2003

TAKAHARA, LIU and YANO

append(As,[A],As2), D:=Fr->dlist, D2:=element(D,A,V,"*"), supL(SupL), if strlen(D2)vlist,[V],Vs2), Fr2->alist:=As2, Fr2->vlist:=Vs2, Fr2->dlist:=D2 end; dom(A,Vs):vLst(VLst), project(VLst,A,Vs); genA(C,As):iap(Iap), As:=Iap; goal([0],0):-!; goal([K|Ks],V):state(K,L), goal(Ks,V2), V:=strlen(L)+V2; goalseeker(CC):xwriteln(0,"pop up,stack"), regG(V), show1(V,plot), if regStack([[C,As]|Stacks]) then assign(regStack,Stacks), sigma(C,As,A,RA,C2), if A<>[] then xwriteln(0,"push down stack2"), goal(C2,V2), append(regG,[V2],regG), genA(C2,As2), append([[C2,As2]],regStack,regStack), else assign(regC,C), end, goalseeker(CC) else regC(CC) end; sigma(C,As,A,RA,C2):delta(C,As,C2), if C2=[] then A:=[],

RA:=[] else A:=a, RA:=[] end; support

getID(ID):currentID(N), ID:=N+1, assign(currentID,ID);

currentID(0);

References [1] Cantone, D., E. Onodeo, A. Policriti, Set Theory for Computing, Springer, 2001. [2] Hooker,

J.

Logic-Based

Method

for

Optimization, John-Wiley, 2002. [3] Mesarovic M. D., Y. Takahara, Abstract Systems Theory, Springer, 1989. [4] Takahara,Y., H. Kubota, “A Framework of Conceptual Design of Data Processing System”, Office Automation, Vol. 10, No. 1, 1988 (in Japanese). [5] Takahara, Y., N. Shiba, Y. Liu, “General system theoretic approach to data mining”, International Journal of General Systems, 2002. [6] Takahara, Y., Y. Liu, J. Hu, H. Shimazu, M. Okada, “Intelligent data mining system”, Proceedings of International Conference on E-Business, Beijing, 2002. [7] Takahara, Y., A. Shimizu, “A foundation of problem

solving

EUD-conceptual

framework”, J. of JASMIN, Vol. 5, No. 3. 3, 1996 (in Japanese). [8] Takahara, Y., Y. Liu, “An extended prolog for end user development”, Proceedings of World Multiconference on Systems, Cybernetics and Informatics, Orlando, 1999. [9] Witten, I., E. Frank, Data Mining, Morgan Kaufmann, 1999.

JOURNAL OF SYSTEMS SCIENCE AND SYSTEMS ENGINEERING / Vol. 12, No. 2, June, 2003

157

A Formal Systems Approach to Solver Design

Yasuhiko Takahara received his B.S. from the University of Tokyo in 1959, his M.S. and his Ph.D. from Case Institute of Technology in 1964 and in 1976, respectively. From 1967 to 1971 he served as a research associate and an assistant professor at Case Western Reserve University. From 1971 to 1979 he was an associate professor of the Department of Industrial Engineering and Management, Tokyo Institute of Technology and since then has been a professor emeritus of Tokyo Institute of Technology. From 1995, he moved to Chiba Institute of Technology and since then has been a professor emeritus of Tokyo Institute of Technology. His research interest is primarily in general systems theory, cybernetic systems and management information system.

and 1994, respectively. From 1994 to 1999 she was an assistant and lecturer at the School of Business and Administration, Central South University of Technology. Since 1999 she has been a Ph.D. Candidate of Department of Management of Information Science, Chiba Institute of Technology. Her major interests are systems theory and management information systems. Yoshio Yano received his B.S. and M.S. from Chiba Institute of Technology in 2000 and 2003, respectively. Since 2003 he has been a Ph.D. Candidate of Department of Management of Information Science, Chiba Institute of Technology. His major interests are systems theory and management information systems.

Yongmei Liu received her B.S. and M.S. from Central South University of Technology in 1991

158

JOURNAL OF SYSTEMS SCIENCE AND SYSTEMS ENGINEERING / Vol. 12, No. 2, June, 2003