--- title: "Representation and Induction of Infinite Concepts and Recursive Action Sequences" authors: - "Fritz Wysotzki" doi: "" url: "https://ijcai.org/proceedings/1983/99" pdf: "https://ijcai.org/proceedings/1983/0099.pdf" venue: "Proceedings of the Eighth International Joint Conference on Artificial Intelligence" year: 1983 pages: "409-413" track: "Learning and Knowledge Acquisition" keywords: --- # Representation and Induction of Infinite Concepts and Recursive Action Sequences Fritz Wysotzki *Proceedings of the Eighth International Joint Conference on Artificial Intelligence*, pages 409-413. ## Abstract A general method for the inference of recursive functions (programs) from examples of computations is described. It is based on the so called algebraic semantics of recursive program schemes and in this paper mainly applied to the representation and induction of infinite concepts and recursive action sequences (which are of importance for problem solving and hierarchical planning). Additionally, the use of recursive program schemes leads to a new principle of generalization in the sense that families of structures or classes of programs could be treated simultaneously and that already existing solutions of old problems could be transferred to new problems which have to be solved. ## Full text ## 1. Introduction Program synthesis by induction as opposed to program synthesis by deduction from input-output specifications becomes a matter of increasing interest in AI and Computer Science. In this field much work has dealt with the synthesis of LISP pro­ grams from examples of computations /3/, /4/' /5/. We are interested on the one hand in the development of a general formalism not de­ pending on a specific programming lan· guage and on the other hand in the induc­ tion of certain infinite concepts and re­ cursive action sequences extending in this way our earlier work on concept learning /6/, /7/. By infinite concepts we mean classes of strings and other stuctures having some intrinsic periodi­ city (In Pattern Recognition only feature vectors of fixed dimensionality have been considered so far). Our method is based on the so called algebraic semantics and recursive program schemes /1/, /2/ and it is intended to provide a general frame­ work for the abovementioned representation and induction problems. The induction principle we introduce in this paper is a more general version of SUMMERS' main syn­ thesis theorem /5/. Our main aim is to apply it to the representation and induc­ tion of recursive action sequences from examples of observed behaviour. This is also of importance for problem solving and hierarchical planning. Section 2 starts with a brief survey on the basic definitions together with exam­ ples taken from the recursive operation of clearing a block and preparing in this way the more detailed discussion of the CLEAR-operator in section 5. In section 3 the induction principle is stated and then applied to two basic examples in section 4 and 5 demonstrating the general method. The consideration of synthesized programs as recursive program schemes (RPS) allows us to introduce a new prin­ ciple of generalization not investigated in AI until now. ## 2. Basic definitions Term algebras, trees, rewriting rules, trogram schemes n the following we use the notations and definitions of /1/. Let Vk = {v 1 , ··· ,vk)' and V = U Vk be sets of variables and F kS1 a set of primitive function symbols with arity or rank {fe-F has arity~{f)). F contains a distinguished symbol ~ representing the ·undefined·. Then let M{F,V) be the set of finite well-formed terms on FuV. Terms are inductively de­ fined by ## Definition 2.1. 1} v E V, x 0 e F 0 is a term {F 0 =constants) - 2) If t 1 , ··· ,tnE M{F,V) are terms then f(t 1 , ··· ,tn)· with fE F, ~{f) = n is a term. Terms can be represented as trees. Example 2.1. The term g{r{v 1 ), v 2 , h{f{v 1 ), g{r{f{v 1 )), v 2 , ..n. )) ) with f, g, r, h E F, f {f) = 1, f{g) = 3, fj {h) = 2 is the tree ![Image](https://ijcai.org/proceedings/1983/fulltext/99/image_000000_0a6ce622a2b343a65d9b59c829cbb958853a46f863239b6922816e90551f6e0e.png) (For the interpretation as a partially de­ fined program for clearing a block see ex­ ample 2.4.) ## Definition 2.2. On M(F,V) a partial order< is defined, intuitively: t~ t' if t' can be generated from t by substitution of ..n. by terms #.D.. at some positions in t · ..D.. is the least element of-<. Every directed subset A' M( F, V) has an upper limit Sup(A) which is a finite or infinite tree. This allows one to extend M F V to the Moo F V of infinite trees w ic we wi esignate y as oppose to finite trees t). In addition to the primitive function sym­ bols f€ F we consider a set ~={� 1 , ··· ,GJ of function variables with a rity 9 (Gi) = = ki ~~~~~r~~~;m;~~er on play the role of Let MIXl(F v lf,v) be the term algebra ex­ tended by ID· ## Definition 2.3. A recursive prosram scheme (RPS) is a pair < ~ , t > consisting of a system of equations t. € M( F u ~, V k ) · and a term t e: M(F v f, Vk), Gi E f, l. i t plays the role of the "main program", which is composed of the "subprograms" Gi mutually "calling each other" by means of r: · ## Exam~le 2.2. (For the interpretation as a program of clearing a block see ex. 2.4) A system ~ can be "solved" using the fol­ lowing rewriting rule by which function variables in the ti s can be iteratively eliminated. Definition 2.4. (rewriting rule) By this definition we allow in a tree t subtrees beginning with function vari~ abies G E ~ to be substituted by other trees Q(G} (which appropriate correspon­ dences . in the variables). Formally: A tree t is transformed into another tree B(t) inductively defined by - 1) §(x) = x if x e F 0 v V A 2) ~<f<t 1 , ··· ,tk>> = f(e(t 1 ), ··· ,Gctk>> In 3) the r.h.s. means that in the tree Q(G) the variable v 1 is to be replaced by Q(ti), 1 ~ 1 ~ k. (Note that ~(ti) = ti if ti contains no function variables.) Instead of ~(t) we will also write if in t Gi is to be replaced by tj. Example: se~ example 2.3 ## Definition 2.5 Let~ be a RPS as in def. 2.3. For 1~i~n and l = 0, 1, 2, ··· we define a sequence Gp) by using the substitution rule of def. 2.4. This sequence is called KLEENE-sequence. It can be shown that Gp>-< GF+ 1 ), l = = 0,1, ··· and that S~p GP)=DfT(! ,Gi), 1 ~ i ~ n is the fixpoint solution (least solution) of l: ## Example 2.3. using the rewriting rule of def. 2.4. with Q(t) = G(l+ 1 )(v 1 ,v 2 ), Q(G) = G(l)(v1,v2). Note that this KLEENE-sequence is genera­ ted by the following procedure which we will use for induction(8section 3): There is a tree tr = G 1 = g{r{v 1 ), v 2 , h(f(v 1 ),..n.)) and a fixed node min tr (labelled by .n.) and G{ 1 + 1 ) is construc­ ted b} substituting G{l) [t/~J = = G{l (f{v 1 ), v 2 ) at node m ( 1 = 2,3, ··· ). G(l) [t/~J means that the , vector of vari­ ables~= (v 1 ,v 2 ) of G(l) has !o be re­ placed by: the vector of trees t = = {f{v 1 ), v 2 ). Interpretation and valuation Until now we have considered syntactical structures only. By an interpretation I we assign to every function symbol f with arity i a function on some domain (D x D x ··· x o )I. {We have to take v1 v2 vi into account sorted functions and vari· ables v 1 , ··· ,vi). .< is interpreted by :: I, ..Cl.. by .L (the "un­ defined·). An interpretation assigns to each RPS a program. By a valuation ¥ we assign to each variable v. a value rom Jdomain {Dj)I. An interpretation together with a valuation assigns to a RPS a value (the result of the computation by~~ Examfle 2.4. (see fig. 1 and example 2.2.) Let , F£ F be the truth values ·true· and "false· 0 respectively and in example 2.2. g be the McCARTHY-conditional ( <F denotes interpretation) Let v 1 be a variable denoting definite objects x (blocks), r(x} the predicate CT{x) = cleartop (x), f{x) the logical function Lu(ON{u,x)) ("that block u lying on block x·), v 2 a state variable s and h(x,s) 4:= put (x,s) ("put x in state son the table" getting the new states'= put (x,s)). Then �{v 1 ,v 2 )~ CLEAR (x,s) is the (recursive) CLEAR-operator· In the case of fi~. 1 we have 2 CLEAR (x,s) = put {f{x), put (f (x}, g(CT{f 2 (x)),s, ··· ) ··· ) = put (f{x), put {f 2 {x},s)) since g (CT{f 2 {x)), s, . ··· ) = s Fig. 1 Clearing a block Xf f{x) =of t. u{ON{u,x)) { L : jota operator) ![Image](https://ijcai.org/proceedings/1983/fulltext/99/image_000001_6510dc8fc65f0478375629f0f1b064c0359267d6393ec73b2c3c233b8117eeed.png) ## 3. Principle of induction Our main aim is to construct {recursive) programs from examples of computations. The induction principle is a generaliza­ tion of the synthesis theorem of SUMMERS /5/. {The convergence properties areal­ ready established by our use of the KLEENE-sequence, def. 2.5., for induction.) In the first stage we build from a finite set of examples a finite tree ~ either by a learning algorithm or by a combination of alternatives similar to /5/. Then we try to interpret i as an element of a KLEENE-sequence of some RPS which has to be induced. Formally: If there exists a tree tr · M(F~~,V}, a fixed node min tr, a vector t =.(t 1 , ··· ,t ) of trees tiE M(Fu ~. V} {1 = 1, ··· ,R) and a se­ quence then we consider ~ as~the l·th element of a KLEENE-sequence. t(t/v] means that the vector v of variables of t has to be re­ placed by the vector rand tr{t/m) means that m is the root nod~ of subtree t in tr. (In general the t(lJ 's are defined only for some specific values of the vis and the domain has to be extended by the induction process.) The method can be generalized to the case where several nodes mk in tr have to be replaced by ·macro-functions· (see section 5). Having established t as t(l·} and 1· being suf­ ficiently high we extrapolate the sequen­ ce for all l and get the simplest hypo­ thesis (i. e. RPS) which has ~ as the l·th element of its KLEENE-sequence. 1· can be regarded as a measure of the reli­ ability of the hypothesis. In sections 4 and 5 we demonstrate the method by two basic examples. ## 4. Induction of recursive Boolean expressions We consider the following classification problem on the set{a 1 a 2 ··· akl k=1,2 ··· J of binary strings {aj £ {0,1) for 1~j; k): all strings with ai = 1 for i = 1, ··· ,k belong to the class T ("true·) and all other strings (i. e. containing at least one aj = O) belong to the class F {"faa~~ From a finite training sample of strings the algorithm has to infer the classifi­ cation function for strings of arbitrary length. Our set of primitive functions g, x, r, s e F (flee section 2) is defined as follows · Definition 4.1. g is the McCARTHY conditional as in ex. 2.4. s(k) = k + 1 k = o, 1, 2, ··· x(i), r(j) are tests to be performed on strings, s is the successor function, T, F€ F 0 are the truth values for tests as in ex. 2.4. Suppose we have a training sample of all strings up to length k = 2, strings consisting only of symbols 1 being classi­ fied as T, strings containing at least one 0 as f. Then by a slight modification of an algorithm for automatically construc­ ting decision trees from training s~mples of feature vectors /6/, /7/ the following initial tree ~ can be built This tree classifies (by definitions 4.1.) the strings 1 and 11 as T, ~11 other strings with length ~ 2 as F and strings with length> 2 asA. According to section 3 we have to search for a tree tr which appears as a subtree of itself (at a fixed node m) r~cursively with appropriate substitutions t/V of va­ riables. (That is we use a matching pro­ cedure with appropriate replacement of variables.) Observing the "periodicity" of the appear­ ance of the symbols r and x respectively in ~ at the same position in subtrees be­ ginning with g we define with G( 1 )(s(1)) = G( 1 )(2) = g(x(s(1)), g(r(s 2 (1)),..n, i'), F) That is we have for 0 ~ 1 ~ 1·, 1· = 2 a KLEENE.sequence which is partially defined for 1 "S ti ~ 111! - (1 - 1) (1 = 1,2; 1· = 2) and undefined for other values of n. In the sense of section 3 we have (fo~ n = 1,2) tr = g(x(n), g(r(s(n)), c, T), f) .. and t = t = s(n). c is an arbitrary tree labelling 1 the node m mentioned in section 3. Now we want to get the simplest hypothesis for continuation of the KLEENE-sequence. The simplest hypothesis is to extrapolate G(l) for all 1 and fpr all n (i. e. extending the domain) using the successor function s(n) on the natural nu"mbers.This way we get the recursive program G(1) accepts (classifies) all strings ~ containing only 1's as T arr-others as r and our starting tree 1 is the second element of its KLEENE-sequence. (With other words: 2:: accepts for n = 1 a log,. ical conjunction of arbitrary length. For n> 1 the first n - 1 elements of a string are ignored.) Note that the reliability of the hypothesis is low because we have used examples up to 1· = 2 only. Fig 2 Chain and c1rcuit ![Image](https://ijcai.org/proceedings/1983/fulltext/99/image_000002_b5845f9874e7d38b3942559db808be625eb9b23e0f8d41f42a8c099ae9067b8d.png) Now we introduce a new principle of gene­ ralization. We abstract from the interpre­ tation of the function symbols G, g, x, r, T, F used so far (see def. 4.1.) and con­ sider r as a pure syntactical structure (i. e. RPS). If we interpret\_g, x~ r as in def. 4.1. but T by F and F by T thenX accepts all strings consisting only of 1~ as F and all others as T. If we addition­ ally interpret x by"'x (negation of x) then ~ accepts all strings containing at least one 1, i. e. a logical disjunction of arbitrary length. With another inter­ pretation of x, r, we could makei. accept all graphs consisting of a directed chain (fig. 2a) and with still another inter­ pretation all directed circuits (fig 2b). This means that L read as a RPS accepts families of structures which can be con­ sidered as being equivalent in this sense. This could be used to avoid the full in­ duction process for a new problem for which one has a starting tree~. Before performing the induction one could try to find a structural isomorphism of ~ with an element of a KLEENE-sequence of an al­ ready existing RPS (solution of an old problem) being at the same time a syntac­ tical solution of the new problem too. ~that this procedure may also be re­ garded as some kind of analogical reason­ ing in which functions (or relations) would be replaced by other functions (relations). ## 5. Learning action sequences Now we consider a more complicated exam­ ple in which several nodes mk in the tree tr (see section 3) have to be replaced by "macrofunctions". We return to the problem of clearing a block x (fig. 1) which we have dealt with in examples 2.2. - 2.4. The variables and primitive functions are as in ex. 2.4. Suppose we have the follo­ wing three examples of observed behaviour (training instances): CT(x) ~ s (·if clartop (x) then nothing is to be done·) CT(f(x))\_. h(f(x}, s) (·if the block f(x} lying on x is clear then put f(x} on the table in state s·) Combining these alternatives by means of the function g to a initial tree ~ leads to From the first position in each subtree beginning with g we get the sequence CT(x}, CT(f(x}}, CT(f 2 (x)) and define With this definition we get from the se­ cond position in the subtrees beginning with g the sequence s, h(F(1,x}, s}, h(F(1,x), h(F(2,x}, s)). The simplest hypothesis is to continue by h(F{1,x), h{F{2,x), h{F(3,x), s))}, ··· i. e. by using the successor function s(n) for extrapolation. With a function the above sequence can be written as H(n,x,s) =of H'(1,n,x,s}; H(O,x,s) =of s (5.4} A and the tree t (5.1) as The simplest hypothesis is again to ex· trapolate by means of the successor func­ tion. Using the induction methods intro­ duced in section 3 and 4 we get this way a KLEENE-sequence G'(l) and the fixpoint solution ## Pro~osition 5.1. G'{ )(O,x,s) reproduces the tree i (5.1) Proof: By def. 2.5. of the KLEENE-se­ quence and use of (5.2) - (5.4). G'(O,x,s) clears a block x from an arbi­ trary number of blocks (fig. 1). Finally we compare the representation G' (5.6) of the CLEAR-operator with the re­ presentation G introduced in examples 2.2. and 2.4. which is the minimal one (but not easy to learn). The equvalence of both representations is established by the following ## Proposition 5.2. There exists a syntactic transformation which transforms G' into G. Proof: By proving that each element G,(l) of the KLEENE-sequence of G' can be trans- formed into the corresponding element G(l) of G using the reduction rules repeatedly. These rules could be made clear from the semantics in ex. 2.4. c~ means that the l.h.s. of the rule can be replaced by the r.h.s.) ## 6. Conclusion A framework for representation and in­ duction of infinite concepts and action sequences has been represented. It was applied to examples taken from typical AI domains, demonstrating the general con­ struction algorithm. The induction prin­ ciple was formulated with the help of the KLEENE-sequence. Equivalently the concept of a tree grammar could have been applied, i. e. our induction problem is equivalent to the problem of identification of a tree grammar. In our examples we have dealt with the construction of single loops only, multiple (nested) loops can be treated by a more step procedure in a similar manner. The use of program sche­ mes (RPS) instead of programs allows one to treat classes of functions simultan­ eously. This can be used to avoid the full solution of new problems if there exists already program schemes isomorphic to the111. In future work we will investigate broad­ er classes of functions playing an impor­ tant rols in AI research especially in picture recognition and planntng. ## References 1. / Courcelle, B. •Infinite trees in nor- mal form and recursive equations having a unique solution.• Math. System Theory 13 (1979), 131-180. / 2. / Courcelle, B.; Nivat, M. "The algebra- ic semantics of recursive program sche~es.• In: Math. Found. of Comp. Science 1978 (W inkowski eds.), Lecture Notes in Comp. Sciences,Vol 64, Sprin- ger-Verlag, New York 1978, 16-30. / 3. / Jouannaud, J. P., Guiho, G. •Inference of functions with an interactive system.• Machine Intelligence 9 (19791 227-250. / 4. / Jouannaud, J. P., Kodratoff, Y. •characterization of a class of func- tions synthesized from examples by a SUMMER S-like method using the "B.M.w.• matching technique.• In Proc. 6, IJCAI, Tokyo 1979. / 5. / Summers, Ph. o. •A methodology for LISP program construction from exam- ples." J. ACM 24/1 (1977), 162-175. / 6. / Unger, S .; Wysotzki, F. •Lernfahige Klassifizierungssysteme." Akademie- Verlag, Berlin 1981. / 7. / W ysotzki, F.; Kolbe, W.; Selbig, J. "Concept learning by structured ex- amples-an algebraic approach." In: Proc. 7. IJCAI, Vancouver 1981.