On the Descriptional Complexity of Production Systems

1 Introduction

In (Georgeff, 82) a production system architecture is described in which procedural knowledge is specified by control languages. In this framework he outlined transformations on production systems to remove the amount of nondetermism to get a more efficient execution. In order to clearly separate the means for describing control knowledge from the (object-level) semantics of a production system and to compare different methods to describe controlknowledge we will abstract this concept by production system schemes. Different methods to describe control information in production systems can then be modelled by different classes of production system schemes (this is in parallel to the theory of program schemes (Greibach, 75)). The concept of production system schemes might also form the basis for a theory of transformations on production systems. In this paper we consider the following classes of production system schemes: controlled production system schemes in which procedural knowledge is described by languages and production system schemes with markers, which use special database symbols to sequence the order of productions. These classes of production system schemes will be compared from the viewpoint of descriptional complexity. We show

ON THE DESCRIPTIONAL COMPLEXITY OF PRODUCTIOIN SYSTEMS

Peter Trum Battelle-Institut e.v. Am Roemerhof 35 D-6000 Frankfurt am Main West-Germany

that removing nondeterminism (if possible) in controlled production systems might result in a size explosion of the equivalent deterministic production system. In the same way we show that in some cases the specification of control­ knowledge by markers can result in drastic more succinct representations than a separate description of controlknowledge in even non­ deterministic controlled production systems.

2 Notations and Definitions

In the following definitions we introduce the concept of (controlled) production system schemes and production system schemes with markers.

Def.:

A production system schema ( PSS) ·is a quadrupel Q = (r: , P, A, f) with '[ a finite set of production symbols, A a finite set of action symbols, and f a function from '[ into (PU~)*x A with P {plpEP}denoting the set of

negative predicate symbols. For s in '[

f ( s) = ( c, a) is denoted by c ---+ a where c is the condition (to be interpreted as the conjunction of its elements) and a the action of s.

Def.:

An ~nterpretation of a PSS Q = ( r:, P, A, f) is a pair I = (D, h) where D is a nonempty set, the database of Q, and h is a mapping assigning to each pEP a predicate h(p) from D into {O,l} and to each a ~A a relation over D.

Def.:

A controlled production system schema (CPSS) is a pair Q = (L, P) where P is a PSS and L a language over the production symbols of P.

Def.: Let 0 = (L, P, A, f) be a PSS, C = (L, O) be a CPSS and I = (D, h) an interpretation. The execution relation

=> over

(NLxD)2 where NL denotes the set of all prefixes of words in L is defined as follows:

v s ~ L, vx1, x2 c: o2: (u, x1) => (us, x 2) iff f ( s) = q -+ a, h ( q) ( x 1) = 1 and (xl, x2) ( h(a). The relation I(C) computed by C under I is defined as I (C) = {(x, y) / ( 1: , x) ~ (w, y), wEL } ·

Let 01 and 02 be two CPSS's. Then Ol and 02 are equivalent iff I(Ol) = I(02) under every interpretation I.

The above definitions describe how the execution is controlled by a language. Another method to specify control in production systems consists of allowing the productions to assert certain markers into the data base that then can be tested by other productions.

This can be formalized as follows:

Def.: Let M = { vl, ··· , Vn } be a set of markers and V = {m1, ··· ,mk} be a set of values. For vi f M and mi .c. V we' 11 denote by Vi = mi a new pred1cate symbol with negation Vi*mi and by Vi<­ mj a . new action symbol with the fixed mean1ng: "assert that vi has value mj

into the database".

Def.:

A production system schema with markers (MPSS) is a tuple 0 = ( L , P, A, M, V, f) with L , P, A defined as for production system ·schemas, M a set of markers, V a set of values for markers in M and f a function from L into the set <;ui>u {v = mj, vi* mj/vifM~ mjE:V) x( AU {vi<- mj/vi':M, mj C:V } ) ·

The definition of execution under an interpretation I = (D, h) must be modified in the obvious way so that the meanings of the new predicates and actions are fixed (see e.g.

Engelfri·et, 74).

In the following we will restrict ourselves to regular control languages. In order to compare the sizes of production systems we next introduce our size measures. Clearly the size of a PSS P is given by the number of its productions. In the case of a CPSS we also have to measure the control language complexity. This can be done by the size of the automaton accepting

this language. For a regular control language L the number of states in the nondeterministic (NFA) or deterministic (DFA) finite automaton M accepting L then is a good measure for the descriptional complexity of L (in this case Lis also denoted by T(M)).

3 Main Results

If only one production application at each execution step of a CPSS 0 = (L, P) can eventually lead to a successful termination, then it's possible to translate it into an equivalent deterministic production system. If in addition the control language is regular we can transform the production system into an equivalent flowchart program.

It is easy to show that in such cases the number of states in the DFA M accepting the language s(L) gives us the size-complexity (i. e. number of statements) of the equivalent flowchart program where s denotes the following substitution from the production symbols into the predicate

and action symbols of P:

s(p) qf where f(p) = q -->f

Theorem 1

For all n ~ l there exists a CPSS Pn with size complexity O(n) s. t. every equivalent flowchart program On has a size complexity of at least 2n.

Proof:

Let Pn be defined as follows:

Pn = (Ln, On) where On = ( {pl, P2, P3}, {p,<U {gl, g2}, f) with: f(pl) pq -+gl, f(p2) = pq -+g2, f(p3) = pq -+nil, Ln = {pl, P2}*·{ Pl} · {pl, P2 }n-l · t1'3J.

Now it's easy to see that Pn allows

for deterministic execution and that

s(Ln) = {pqgl, pqg2 }.{pqgl} {pqn, pqcn}n-1 {pq}

Since Ln can be accepted by a NFA with O(n) states it also follows that the (nondeterministic) description of Pn has a size complexity of O(n). On the

other hand it can be shown (Trum, Wotschke, 83) that each DFA M with T(M) = s(Ln) needs at least 2n states prooving our theorem.

If we consider a MPSS Q with a markerset M the execution order of productions is only constrained by the testing/setting of markers (i. e. the control language is E*). But, as shown in (Engelfriet, 74), the constraints introduced by the use of markers can be modelled by a regular controllanguage CM. This means that in such cases the control language is defined in the productions themselves. This leads us to the following characterisation for the equivalence of MPSS's and CPSS's:

Theorem 2

Let Ql be a MPSS with markers in M and 02 = (L, P) be a CPSS. Then 01 and 02 are equivalent if s(L) = h(s(CM)) where h is the following substitution: h(vi = mi) = h(vi =* mj) = h(vi <- mj) = e and n(a) = a otherwise.

This result leads us to our last theorem:

Theorem 3

For all n~ l there exists a MPSS Pn with size complexity O(n) s. t. every equivalent CPSS Cn has a size complexity of at least 2n.

Proof

Let Pn ( E, P,A,M,V,f) with P = {p }, A = {gl I g2 } I M = {q,vl·····vn}, V = {1, ··· 2n+l }, L = {pl, .·· ·P2n+l· Pl· ··· rP2n }and f defined as follows:

f(pi)

f(Pn+i)

(q = i "P .... q <- i+l " Vi <-

(q = n+i A Vi

1

"

"

for 1 :> i :> n and

f(P2n+l)= (q = 2n+l -+nil).

Furthermore, the initial value for the markers is 1 and the goal state is any state where q has value 2n+l.

1 .... q<-n+i+l Since we do not allow to introduce new predicate or function symbols, any equivalent CPSS Cn = (Ln,On) without any markers can have only productions of the form c ~a where c E{ p,p } and a r::{gl, g2 }

Because of theorem 2 these productions have to be sequenced by the language Ln s.t. s(Ln) = {w1w2/w1 E {pgl, pg2 }n, W2E: {gl, g2 } n s.t. h(wl) = w2 where

h(p) = h(p) = g2 } = Ln.

For any language Ln with s(Ln) = Ln it holds that any pushdown automaton accepting Ln needs 2n state or stacksymbols (Meinecke-Schmidt, 78) no matter how the productions in On look like. From this it follows that the specification of the control language by even more general context - free rewrite rules (meaning that the control language itself is specified by a production system) requires 0(2n) productions, thus prooving our theorem.