TH E UN I V E RS I T Y O F M I CH I G AN COLLEGE OF LITERATURE, SCIENCE, AND THE ARTS Computer and Communication Sciences Department Computer Information and Control Engineering STRUCTURAL INFERENCE AND IDENTIFICATION OF DISCRETE TIME SYSTEMS Anna Sylwia Zalecka-Melamed July, 1977 Logic of Computers Group Computer and Communication Sciences Department Technical Report No. 200 with assistance from: National Science Foundation Grant No. MCS 76-04297, Air Force Office of Scientific Research Grant No. 77-3160

ABSTRACT STRUCTURAL INFERENCE AND IDENTIFICATION OF DISCRETE TIME SYSTEMS by Anna Sylwia Zalecka-Melamed Co-Chairmen: William A. Porter, Bernard P. Zeigler This dissertation develops a general theory of coordinatized sets and structured functions. This theory is then applied to structure inference and identification of discrete time systems with coordinatized state spaces. The aforementioned inference and identification are based on partial data produced by the system. To every set of experiments there corresponds a family of structured partial models of the system. As experimentation progresses, a sequence of families of partial models is obtained. Those models and their interrelations are studied. Several measures of model performance such as structural confidence, predictive range and confidence are introduced. Properties of these measures and their dependence on parameters are discussed. We show that the structural confidence measure for a sequence of partial models never decreases as the partial data set grows. We show how the system model can be identified on special subsets

of the state space, given certain complexity bounds on system structure. The construction of a parameterized family of such subsets with desirable properties is described and their computational properties investigated. Several experimentation strategies are suggested and their advantages and disadvantages discussed. A novel feature of these strategies is that they employ a methodology for predicting not-yet-observed state transitions which can be formally justified. Finally, we point out that the theory developed provides a basis for computer aided methodology of model structure inference.

STRUCTURAL INFERENCE AND IDENTIFICATION OF DISCRETE TIME SYSTEMS by Anna Sylwia Zalecka-Melamed A dissertation submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy (Computer Information and Control Engineering) in The University of Michigan 1977 Doctoral Committee: Professor William A. Porter, Co-chairman Associate Professor Bernard P. Zeigler, Co-chairman Professor A. W. Burks Professor J. F. Meyer

In Memory of My Father. ii

Il

ACKNOWLEDGEMENTS I wish to thank the many people who helped me in the course of my studies. I am very grateful to my co-chairman William Porter for his most kind treatment, encouragement, help and time, he never failed to have during my doctoral work. I am equally grateful to my co-chairman Bernard Zeigler, whose work this thesis emerged from, for the guidance and inspiration he provided, for the many hours of discussions spent with me and for the many ideas he suggested. I thank Arthur Burks and John Meyer for serving on my doctoral committee and for the various ways in which they helped during all stages of this work. I thank the Logic of Computers Group and the Air Force Office of Scientific Research for their support. I also thank Alice Gantt and Janet Walters for the careful typing of my thesis. I wish to thank Bertram Herzog who was so helpful in the very beginning of my graduate studies. I am very grateful to Enid and Bernard Galler for being always there, when needed, and for help and encouragement in so many different ways during my stay in Ann Arbor. I wish to thank Rebecca Zeigler, who made me feel at home during my stay in Israel, while completing my research. iii

Finally, I would like to extend my thanks to my family and relatives: to my parents for encouragement and support during my school years; to Felicja Stammer and Aron and Asia Wajskol for continuous moral support and encouragement, when there seemed no end in sight; and lastly to my husband, Benjamin, for his encouragement, help and support. I also express my appreciation for his muted complaints, when so many dinners were never cooked and for doing the dishes, when they were. The research reported in this dissertation has been supported in part by: National Science Foundation Grant No. MCS76-04297 and Air Force Office of Scientific Research Grant No. 77-3160. iv

TABLE OF CONTENTS DEDICATION........................... ii ACKNOWLEDGEMENTS......................... iii LIST OF ILLUSTRATIONS.vii LIST OF APPENDICES.ix LIST OF SYMBOLS......................... x CHAPTER I. INTRODUCTION....................... 1 1.1 Review and Motivation........... 1.2 Organization................... 6 1.3 Some Notational Conventions............. 7 II. THEORY OF COORDINATIZATIONS. 8 2.1 Introduction................... 8 2.2 Types of Coordinatizations............. 9 2.3 Relations among Coordinatizations. 31 2.4 Theory of Irredundance............... 45 2.5 Conclusions..................... 57 III. FUNCTIONS WITH STRUCTURED DOIAINS............ 60 3.1 Introduction..........60 3.2 Properties of Function Restrictions to a Family of Nested Domain-Subsets.61 3.3 Properties of Extensions of Functions Defined on Proper Domain-Subsets....... 77 3.4 Construction of Domain-Subsets with Special Properties................. 88 IV. LOCATION INFERENCE................... 105 4.1 Introduction................... 105 4.2 Confidence in an Inferred Location.106 4.3 Prediction Range and Correctness.......... 132 v

V. APPLICATIONS TO DISCRETE TIME SYSTEMS.. 141 5.1 Introduction.141 5.2 Structured Functions................ 142 5.3 Structured Partial Models.............. 145 5.4 Strategies for Experimentation........... 158 VI. CONCLUSIONS....................... 167 6.1 Summary....................... 167 6.2 Suggestions for Further Research.......... 168 APPENDIX............................. 169 REFERENCES............................ 175 vi

LIST OF ILLUSTRATIONS Figure 2.2.1 An Open Circle in R2 Is Irredundant........... 20 2.2.2 Every Open Convex Set in M2 Is Irredundant........ 20 2.2.3 A Graphical Representation of S........... 28 2.2.4 Properties of S with S.E.P.. 28 2.2.5 S Has E.P. and SC Has E.P. for Any Cycle c.. 32 2.3.1 Spectrum of Coordinatizations (No Constant Coordinates).. 34 2.3.2 Broken Lines of Length k Connecting xi and xi+l 44 2.3.3 Illustration of the Proof of Proposition 2.3.2.. 44 2.4.1 Graphical Interpretation of Irredundance......... 49 2.4.2 Irredundance of S1,S2 Implies Irredundance of S1 X S2. 49 2.4.3 Irredundance of Union of Sets.. 52 2.4.4 Irredundance of X Does Not Imply Irredundance of Its Complement............ 52 2.4.5 Illustration of the Proof of Lemmna 2.4.1.... 58 2.4.6 All Supersets of (X<a - XC ) Are Irredundant, ctED oED Where C S..................... 58 3.2.1 Illustration of Example 3.2.1.............. 65 3.2.2 Illustration of Example 3.2.2.a).67 3.2.3 Illustration of Example 3.2.2.b)............. 67 3.2.4 Graphical Illustration of Lemma 3.2.2......... 71 3.3.1 Tables of Functions of Example 3.3.1.... 85 vii

3.4.1 4 Subsets of S....................93 3.4.2 Relative Size of YY as a Function of m......... 103 n-i 4.2.1 Function Tables of Example 4.2.1............. 123 4.2.2 Tables and Functions of Example 4.2.2.......... 133 4.3.1 Illustration of the Proof of Proposition 4.3.2.139 5.2.1 Diagram of a Structured Function............. 144 5.2.2 Illustration of Example 5.2.1.............. 144 5.3.1 Tables of Functions of Example 5.3.1............. 149 A.1 Irredundance of Convex Subsets of Ra2. 172 viii

LIST OF APPENDICES APPENDIX A. IRREDUNDANCE OF CERTAIN {n SUBSETS............. 169 ix

LIST OF SYMBOLS Symbol Meaning D index set P a projection onto ot-coordinate PD1 projection onto D' subset of D basic partition induced by D' on S D' < refinement relation or inequality symbol C set inclusion e.p. extension property s.e.p. strong extension property G(S) graph of S L(l) set of locations of 11 fix restriction of a function f to X lHf partition of kernel equivalence of f L(f) set of locations of f L(f) unique location of f F (S,R set of all functions from S to R Ef(X) Ef(X) set of all extensions f of f from X to S,fEF(sR) (S,R) (S9R) Ef(X) (L,-) set of all extensions f of f from X to S s.t. ES1,R)(S,'. fEF (S R) and LcL(f) ~f(X) _ _f(X) E ( ub) set of all f s.t. fEE(S) and there is an rEL(f) s.t. l|~ g ub

COMP ( X) completion of X w.r.t. L and S F(X,R) (La) set of all functions f in F(XR) s.t. LEL(f) F(XR)C('ub) set of all f in F(X R) s.t. a an LEL(f) with ILI < ub F(X,R) (Lub) F(X, R) (L,) n F (X R) (,ub) X I{s | ssE and PD-L(S) = PD-L(y)} y U XL, where Lk = {LIL C D and ILI = k} LcLk n cardinality of D CONF( CX(L,ub) confidence that L is a location of actual f under ub (S,R)C condition, where f E (X) (SER) CONF (L) CONF(X) (L,ub), when ub = n = IDI (S,R) (SR) ACONF SR)(ub) average confidence on X relative to ub f X) EXPL(S,R) (L) explanatory range of f relative to L f (X) PRED(SR) (L) predictive range of f relative to L PCONFS(R) (L) predictive confidence of f relative to L VAL(SR) (L) validity range of f w.r.t. L P(A) probability of an event A P(AIB) probability of an event A under condition B E(X) expected value of a random variable X IR reals Bnd(S) boundary of a set S Int(S) interior of a set S xi

CHAPTER I INTRODUCTION 1.1 Review and Motivation In many real life situations, we deal with systems for which only partial data is available to construct a system model. We often restrict our attention to a subclass of all possible models, constrained by considerations of elegancy and the sheer necessity to substantially cut down the search space to be explored. In this context we consider the problem of modelling autonomous discrete time systems, with special emphasis on structure inference and identification. It is assumed that the state space of the system is structured (coordinatized). Each system state thus is a finite tuple, where the coordinates represent the chosen attributes of the system. Examples of such a system are: a bacterial cell, specified by the set of vectors giving the concentration levels of chosen molecule types and their transitions ([Zl]), digital networks ([HS1]) and tessellation automata ([YA1]). Systems with coordinatized state spaces have been discussed in [K1] and [ZW1]. Klir ([K1]) talks about the need for classifying appearances of observed attributes as an important aspect of any empirical investigation. He discusses the level of refinement (resolution level) used in observing system attributes. Zeigler and Weinberg ([ZW1]) use the

above system description in simulation of a living bacterial cell (E. coli). In this work we shall not be concerned with the way in which system attributes come about, but simply assume that they have been chosen and can be measured. In a typical modelling situation, we seek structured models, whose state spaces are identical with the one assumed for the system and whose transition functions have been structured. Essentially, this means that the global transition function is thought of as composed of local (component) transition functions. With each coordinate transition function there is associated a subset of coordinates (its "influence set") such that the knowledge of the present states of "influencers" is sufficient to determine the next component state. A given transition function can be structured in many ways. We will refer to a family of influence sets (one influence set for every component) as a model structure. In general we must explore a multitude of structured models for a given system. It is here that the choice of coordinatization can have important ramifications for modelling. Of special importance are the irredundant coordinatizations, which guarantee the uniqueness of a structured model with minimal interaction (i.e. minimal influencer sets). We discuss various kinds of coordinatizations and their relationships. We also introduce a hierarchy of coordinatizations and discuss methods of irredundant set generation. The framework used follows that of Zeigler ([Zl],[Z2]), where a formalism for handling structured automata is developed. Zeigler discusses coordinatizations of abstract sets and introduces the concept of

structured functions. He points out potential implications for modelling of a state set coordinatization used. After every set of experiments (or every data generation phase) we can construct a family of structured partial models —partial in the sense that in general they are defined only on a proper subset of the system's "operating range". This subset always includes the set of states visited in previous experiments and all partial models match the real system behavior on the latter set. Partial models and various proposals for their performance evaluation and comparison of rival models have been discussed in [M1], [H1] and [G1]. Maciejowski ([M1]) suggests that the problem of choosing between rival models is the same as that of assessing confidence in the models —the model, in which one has higher confidence is the one to be preferred. Hanna ([H1]) suggests evaluation of learning models based on the information content of a model. Gaines ([G1]) proposes model evaluation based on complexity, with preference for less complex models. He also points out a trade-off between complexity of a model and the degree to which it approximates a given behavior. We are interested in experimentation and construction strategies, which efficiently generate "credible" models. To this end, we define a probability measure reflecting, for every partial model, the confidence we have, that the total model of the system (i.e. defined on the whole state set) is identical to it in structure. All the measures are defined under the assumption that "everything we have not seen yet" is equally likely to happen. The degree of confidence is also used by Klir ([K2]) to evaluate correctness of structure candidates representing a given data system.

Alternate rounds of experimentation and model construction result in a sequence of families of partial models. In case that each of the experimental sets in the sequence is irredundant, every family consists of just one partial model. We show that in this case, there exists a total ordering (by inclusion) of partial model structures. Moreover, as long as the number of coordinates is finite, even if the state space is infinite, there is a point in the sequence beyond which each partial model has the same structure as the total system model. However, unless an upper bound on structure complexity is known and attained, we do not know at what point the structure has been identified. This result is analogous to results in language and grammar identification ([G3], [Fl]). Gold ([G3]) discusses concepts of language identification in the limit and finite language identification. Feldman ([F1]) discusses grammar identification in the limit and grammar approachability. In case of language identification in the limit, the learner guesses a language at each time. After finite time all the guesses are same and correct, but the learner does not necessarily know when his guess is correct and so must go on processing the information. Finite identification is analogous to our structure identification, when a bound on structure complexity is given and known to be attained. In general, we show that the structural confidence measure for a sequence of partial models never decreases as the partial data grows. We define and discuss several other measures of model performance, in particular predictive range and confidence. Predictions are made for the predictive range of a partial model and are constrained by so-faracquired data. They are made in belief that regularity detected in the data will continue to be present in the behavior of the system on the

predictive range (i.e. that the structure will not change). This is analogous in spirit to a methodology of predictions proposed by Klir ([Kl]). Klir suggests identification of time-invariant properties representing the data, by processing the empirical activity matrix (acquired data). Those properties are then used for generation of activity matrices (further data points). A rule of generation of further data is thus based on the same properties as the empirical activity matrix. We show that the more a partial model is able to predict beyond the experimental set, on which it is constructed (the predictive range), the smaller our confidence must be that what it predicts is correct. But every misprediction on the predictive range is informative —it invalidates the hypothesis that the actual function has same structure as its observed portion, and so forces us to extend at least one of the influence sets. Thus if structural information is our main goal, the larger the predictive range the better. Based on the theory developed, we offer a modeller several experimentation strategies based on various trade-offs between expected confidence, expected predictive range and computational complexity. Some of the strategies proposed use special domain-subset construction methods. Under certain upper bound conditions on system structure, those allow a modeller not only to determine model structure but also system transition function. The theory developed here provides a basis for computer-aided methodology of model structure identification. Feasibility of a software package, aiding a modeller in constructing a system model, is largely due to the simplicity of evaluation of the proposed measures.

The problem of designing computer aids to help the modeller in dealing with plurality of partial models has been raised and discussed by Zeigler ([Z3]). Zeigler points out the requirements that need to be met by such a software system. 1.2 Organization This dissertation is organized in two parts. The first part consists of Chapters 2-4 and is concerned with the theory of coordinatizations and functions from structured domains. Chapter 2 develops a theory of coordinatizations. It introduces a hierarchy of coordinatizations. In particular irredundant coordinatizations are analyzed and ways of generating irredundant sets proposed. Chapter 3 discusses properties of functions from structured domains. We introduce the concept of a location of a function and investigate properties of locations of a function, when restricted to a family of nested subsets. Based on those results we proceed to discuss determination of locations for a finite family of functions on the basis of a proper domain subset. Finally, methods for construction of special domain-subsets of a Cartesian domain with desirable properties are set forth. Chapter 4 addresses itself to the problem of location inference. Methods of location inference for a function known on a proper domain subset only are discussed. Notions of structural confidence, average confidence on a subset, predictive range and predictive confidence are introduced. Computational methods for their evaluation are provided and their properties and dependence on parameters analyzed. The second part consists of Chapter 5 and is devoted to the

application of the theory developed in the first part to discrete time systems. It discusses structured transition functions, i.e. structured functions on coordinatized state space of a system. A concept of a partial system model is formalized and structural confidence, predictive range and predictive confidence for a partial model are discussed. A methodology for predicting state-transitions not yet observed is proposed. Ways of comparing rival partial models are suggested. Finally, several experimentation strategies are proposed and their advantages and disadvantages discussed. The above parts are followed by Chapter 6, which summarizes the results obtained in them and suggests a number of further research topics. Finally, Appendix A discusses irredundance of open convex subsets of fR, with potential applications to identification of stochastic automata. 1.3 Some Notational Conventions Each chapter in this dissertation is divided into sections. Section m of chapter n is numbered according to the scheme n.m. Theorems, lemmas, corollaries, etc. within each section n.m are numbered according to the scheme n.m. 1 and delimited by the symbol 0. Lines are tagged by numbers or lower case letters. References to a line tag made within the scope of a theorem, lemma, corollary, etc., are always local, unless otherwise specified. A referenced acknowledgement is provided whenever a theorem, definition, etc. is reproduced from another source; all other theorems, definitions, etc. are original to this dissertation. The reader is referred to page x for a detailed list of symbols.

CHAPTER II THEORY OF COORDINATIZATIONS 2.1 Introduction In this chapter we develop the theory of coordinatizations of a single set. This development is largely based on work of B. P. Zeigler (see [Z1]). His formalism and definitions are used here as the starting point. The importance of this theory stems from the fact that the type of coordinatization of a state space of a discrete time system has important implications for modelling enterprise. We explore here several types of coordinatizations and their interrelations. The spectrum of coordinatizations, which fall in between independent ones at one end and Cartesian ones at the other, is introduced. Irredundant coordinatizations will be particularly emphasized. Their special importance results from the fact, that when a state space of an autonomous discrete time system is irredundant, there is a unique structured model of this system with transition behaviour identical to that of the system. We will demonstrate ways of constructing irredundant sets, for example using as constructing elements the sets already known to be irredundant, like the Cartesian ones. It is often easier to determine whether a given set is irredundant or not, by looking at the way it is built from basic elements, rather than by using other criteria (like the one following directly from the definition of irredundance).

9 2.2 Types of Coordinatizations The next few definitions and theorems follow those of [Zi], with only minor deviations. We start with a concept of a structured set. A set S is said to be structured if it is a subset of a cross product of an indexed family of sets, that is S C XSS. With a structured set S, we associate a family of coordinate projections {P lacD}, where P:S -+ S is defined in the natural manner. With index set D totally ordered, we extend the projections to project on all nonempty subsets of coordinates. Thus for any D' C D, PD':S - XD S and PD' =X P where the order of coordinates is the aC D 1 ' acD one induced by the order of D. P is defined to be any constant function with domain S. From now on we assume that a set S we are dealing with is structured over a finite index set D, where cardinality of D is at least 2. Definition 2.2.1 ([Z1]) A partition H on S is said to be induced by a subset D' of D, if for every pair x,ycS, xHy iff PD' (x) = PD' (y). We will denote iH as above by IIS, and refer to it as a basic partition on S induced by D'. In case D' is a singleton, e.g. D' = {c}, we will often write HS rather than IH When it is clear what structured set we have in mind, we will S sometimes write HD,, when ID, is actually meant. In general there might be more than one subset of D inducing the same partition on S. In other words the map f:2D P, defined by f:D' '- IHD' is not one-to-one for arbitrary coordinatizations. As we

10 shall see later however, this condition will turn out to be a necessary and sufficient one for S to be independent. We remind the reader that pS denotes the set of all partitions on S and PD the set of all basic partitions on S. When S is a proper subset of XP (S), intervariable dependOtD ence may arise. This leads us to the following definition. Definition 2.2.2 (TZ1]) S S Coordinate caD is dependent on S, whenever i D- n'. Q Coordinate acD is independent, if it is not dependent. We will say that S is coordinatized independently (or is independent) if all coordinates of D are independent. It follows directly from the definition, that coordinate a is dependent on S, if for arbitrary tuple in S, knowledge of its projection onto D-a suffices to determine ct-coordinate value of the tuple. A concept of a location of a partition or function we are just about to introduce will play a central role in this thesis. With every partition 1T on S, we associate a family of subsets of D with special properties-locations of I. Definition 2.2.3 ([Z1]) Let T be a partition on S. D' C D is a location of TI on S, if I., < TI and for any D" C D', if HTS, < T, then D" = D'. 0 We see that a location of IT is a minimal subset D' of D, such that the basic partition associated with D' refines I. In general a partition may have many locations. For special types of coordinatizations though, every partition on S has a unique location.

11 We will call such coordinatizations irredundant. Definition 2.2.4 ([Z1]) A coordinatization of S is irredundant if every partition on S has a unique location. O The next theorem states necessary and sufficient conditions for a set S to be irredundant. Theorem 2.2.1 ([Zl]) A coordinatization of S is irredundant a) iff for all D1,D2 C D, lD1 C = S 1 2 1 rD2 b) iff for all D1,D2 C Dl, 1D 1 where S U 2 is the transitive closure of the set union of T1 and 2 Proof Can be found in [Zl]. c] We remind the reader that if 1l and H are any relations on S, 2 then the transitive closure of 1 and l2, IU 11, is defined by s(11 U IT2)s' sls2,...,s' = s such that s.lls+ for all odd i, 1 2 1 2 n 1 1 i+1 and s.iTsi+ for all even i. Definition 2.2.5 A coordinatization of S is Cartesian if S = XP (S). 0 Cartesian coordinatizations are always irredundant. This is proven in the next proposition.

12 Proposition 2.2.1 If S is Cartesian, then it is irredundant. Proof We need to show that for any D,D CD, %D nD <D IID U %. If I S = 1, S is clearly irredundant. So we assume IS I 2. Let s (ot) for otD1 S,s'ES, where si s'. We define z by z() = D1 (D2,s' (IC) for oe:D-D1 z is well defined and zl s, ziD s'. This follows, since D2 1 2 (D2nD ) U (Do n(1Ds)) and si S s' Thus sltz and zHI s' implies that s(%D U D 2)s', which was to be proved. Q We will now show that for any finite family of partitions on S with unique locations, the location of their intersection is also unique and equal to the union of the locations of all partitions in the family. Lemma 2.2.1 Let I1= {H,I ',...,I n} be a finite family of partitions on S, with the property that Hi has a unique location Li, for all i = 1,...,n. Then the location of iQ i is unique and equal to iJLi. Proof n We begin by showing that for arbitrary location L of nii n n L IL iL. Since HL nll < i, for i = 1,..,n, L contains a location of i., for all i. But Hi's have unique locations and thus L ) Li., Vi, which implies that L -DLi.

13 n a n Since IL i_ Vi i' iHL~ < H.. But [Li n lence L ~~111 n n IJLi contains a location of Hi., say L. Then L D L and since both L n and L are locations of ni, L = L. We showed then that for an arbin n n trary location L of Hi, L D= Li D L holds. Thus L = 4=i is the unique location of the intersection. 0 The next theorem gives several characterizations of an independent coordinatization. We shall denote by PSD the set of all basic partitions on S. We note in passing, that for any D" C D' C D, D, I< D" Theorem 2.2.2 A coordinatization of S is independent a) iff for all OxzD, a is the unique location of H. b) iff for all D' C D, D' is the unique location of ID, c) iff for all D',D" C D, if D" # D' then HD' D D"' Proof a) First we show, that if for VoCD, a is the unique location of H, then S is independent. Suppose S is not independent. Then M3cD s.t. Dl _ < 1. This implies that D-o contains a location for HI, which is distinct from a. But this leads to a contradiction. We now prove that if S is independent, then O is a unique location of H, for all ocD. Suppose this is not the case. Then 3 an aED s.t. a is not a

14 unique location of H. Thus either a is not a location of Ha or a is a location of H, but not a unique one. In either case A L s.t. L is a location of H and aL. This implies that L C D-a, implies that HD- -< TL -, which in turn implies that a is dependent. This however contradicts our assumption. b) Clearly if for all D' C D, D, has a unique location D', then for all acD, Ha has a unique location a. So by part a) S is independent. We need to show that if S is independent, then D' is the unique location of D,, for all D' C D. By part a) we know that independence of S implies that for every aED', Ha has a unique location a. We note that i, = Qn H Using finite induction and Lemma 2.2.1, we show that HD, has a unique location D'. c) We show first that if S is independent, then D' # D" implies #, % TD,,. Since S is independent %, has a unique location D' and HDI has a unique location D". This follows from part b) of the theorem. Since D' $ D", 1, and 1,, have distinct locations and thus cannot be equal. We now prove that if for V D',D" s.t. D' # D", D# ED"' then S is independent. Suppose this is not the case. Then 3 a~D s.t. a is dependent, i.e. HD < a. This implies that H D-0 n Ha n(D-a) (J = 1 D which contradicts our assumption. There are other necessary and sufficient conditions for irredundance besides those of Theorem 2.2.1. Which condition is used as an irredundance criterion depends of course on a particular situation involved.

15 The next theorem states those conditions. Theorem 2.2.3 A coordinatization of S is irredundant a) iff for V iEpS with H I, QD' = L and L < He Dr b) iff for VIEPS, V D1,D2 C D, if IID< H and I iI, then ~D1 ~ D2 Proof a) If coordinatization is irredundant, then any D' s.t. HID' < 1 contains the unique location of H, say L, for any H # I. Since H # I, L $ P. Also clearly HL - 1H and thus QD' = L iD '< We now need to show that if for every H # I, (r D' = L i O IID?,<~ and IL < IH, then S is irredundant. It suffices to show that L is the unique location of H. Suppose L is an arbitrary location of H. Then ~ IT 11 at L. Since HL < H, L contains a location of H, say L. But L L then t L, and since I and L are both locations, L = L. Since D L D L holds, this implies L = L. Thus L is the unique location of b) We first assume that S is irredundant and show that for any n on S, any D1,D2 C D, if ~D I n and ~Dt H, then 4 H. This follows immediately from Theorem 2.2.1, since < H, A% < H 1 2 4 1% U %~ < ] and by Theorem 2.2.1% U1 A = D 1nD2 We now show that if for every H~pS,VD,D C D %D < H & 1D2 < implies iDl fD2 < ', then S is irredundant. Sp i o ra1 2 Suppose S is not irredundant. Then 3 a H on S, H # I, with at

16 least two different locations, say L1 and L2. Then IIL _<, 1IL < 1H. 1 2 By our assumption HL nL < n and thus L1 n L2 contains a location of H. Since L1 D L n L2, L2 D L lnL and both L1, L2 are locations of II, Li = LinL2 and L2 = Lfr)L2. This implies Li = L2, which contradicts our hypothesis. 0 It turns out that for any coordinatization there exists a relation between the number of indpendent coordinates and the cardinality of the coordinatized set. This is expressed in the next proposition. Proposition 2.2.2 ([Z1]) Let {S ItED} be a coordinatization of a finite set S. Let D' C D be any independent subset of D. Then ID'I < IS 1. Proof See [Zl]. Q The implication of the above proposition is that if S is independent, then the cardinality of S is at least one greater than the cardinality of the index set, S is coordinatized over. We will now illustrate the concepts introduced by a few examples. Example 2.2.1 Consider S C {a,d} X {b,e} X {c,f}, where D = {l,2,3} and S = {(a,b,c),(a,e,c),(d,b,f),(d,e,f),(a,e,f)}. First we list all the basic partitions on S. TS = (a,b,c),(a,e,c),(a,e,f), (d,b,f),(d,e,f) TS = I(a,b,c),(d,b,f), (a,e,c),(d,e,f),(a,e,f)

17 S (a,b,c),(a,e,c), (d,b,f),(d,e,f),(a,e,f) 3 T{1 2} - (a,e,c),(a,e,f), (a,b,c), (d,b,f), (d, e, f) I11 3} = J (ab c),(a,ec), (d,b,f),(d,e,f), (a,e,f) {2,3} = (a,b,c), (a,e,c), (d,b,f), (d,e,f),(a,e,f) TH I = (a,b,c),(a,e,c),(d,b,f),(d,e,f),(a,e,f) I{1,2,3} 0 = (a,b,c), (a,e,c), (d,b,f), (d,e,f), (a,e,f) It can be easily verified that S is independent. The easiest way to do it is to use part c) of Theorem 2.2.2. We will now demonstrate that although S is independent, it is not irredundant. To do so, it suffices to exhibit one partition on S with more than one location. Take I =- (a,b,c), (a,e,c), (d,b,f),(d,e,f), (a,e,f) }. S S S S S We check that< and H <, while S, Sand Sdo not 411,2) 42,3] - 1 2 3 refine H. Thus {1,2} and {2,3} are locations of H and S is not irredundant. Example 2.2.2 Consider S = {(a,b,a),(b,b,b),(b,b,a),(a,b,b)}, D = {1,2,3}. We note that P (S) = {a,b}, P2(S) = {b} and P (S) = {a,b}. Clearly, S = P1(S)X P (S) YP (S) and thus by Definition 2.2.5 is Cartesian. a 2 3 Example 2.2.3 Consider any open circle C in R2. C is irredundant. To show that we need to prove that for any x = (x,x ) and any y = (y,y ), where a1 ~2 (1 ~2 x,yzC xli U1 2y.

18 2 2 2 From the definition of a circle it follows that x + x < r Ot1 OL2 and y2+ y2 < r2 both hold. (r is the radius of the circle C.) Hence 1 2 clearly (x2 +y2 ) + (y2 +x2 ) < 2r2 is true. But then either c1 12 cx 2 a2 2 + 2 < r2 or y2 + x2 < r2must hold (or both). W.l.o.g. assume l Y 2 a1 a2 that x2 + Y2 < r2. Let p = (x,y ). peC and pH1 x, p1a y hold. ai1 a 2 a1 21 12 Thus xHa U IT y, which proves irredundance of C. [ For the illustration of Example 2.2.3 refer to Figure 2.2.1. We remark that the above result can be generalized for any open ball in TRn Example 2.2.4 Consider any open convex subset S of the plane, TR2. S is thought of as coordinatized in a natural manner. We will denote the coordinates of D by al and a2' We will prove that such an S is irredundant. For let P1 and P2 be any two points of S. Since S is convex the line segment joining P1 and P2, L is in S. Since S is open, for every x on L there exists at least one open ball with center x conP1,P2 tained in S. We will denote it by B(x). Let V = {B(x) IxEL }. Then clearly V forms an open cover of P1 P2 L. L is compact and thus Y contains a finite subcover of PlP2 P1,P2 L. We will denote this finite subcover by C = P1,P2 {BI(x1),B2 (x2),...,B (xn)}, where x.ILp for i = l,...,n, for some integer n. Without loss of generality we will assume that the enumeration of x.'s is such that d(xi+ P2) < d(x,p2), where d is the usual 1 122 Euclidean distance inTR2. Also we remove from our finite cover all open balls properly contained in other balls. Then any two neighboring balls must intersect, i.e. B(xi) n B(xi+l) # '. If this were not the case the

19 balls would not form an open cover. Choose any zlCB(xl) n B(x2), z2EB(x2) n B(x3),... *z nEB (xn ) n B(x ). Since as was shown in Example 2.2.3 any open ball in JR2 is irredundant, the following holds: P U1 a2 z[ IIaL (Y z...z H U z nll U H na. This in turn 1 2 2 2 1 21 implies that p1H lolJ U H P2 Thus S is irredundant (refer to Figure 2.2.2). Remark We note in passing that the above result can be quite easily extended to.Rn. Namely, every open convex subset of in is irredundant, for an arbitrary integer n. Also it can be shown that n Sn {(P,.s..pn ) IPi > 0, Vi' and Pi g constant} is irredundant. i= For the proof the reader is referred to Appendix A. This fact has implications for identification of probabilistic automata and other types of systems dealing with concentrations, populations, etc. 0 We will now turn to other types of coordinatizations. For lack of a better name we will refer to the first three of them as coordinatizations of type 1, type 2 and type 3. Definition 2.2.6 A coordinatization of S is of a) type 1 if for all acD, 11 U =1 I D-a c b) type 2 if for all D1,D2 C D s.t. D 0 D = ' DIID= 1 - - - 1 2 HDiU H2 c) type 3 if for all HP,HIIIr)nLd, where L is the family LEL of all locations of H.

20 / y pI I I 2 I~a Figure 2.2.1: An Open Circle in (R Is Irredundant. /,/ ' $B(x1) ) S (X..* a,\ 2igure 2 IFigure\.2.2: Eery cpe ConvexSet S iIR Is Iredund \ant,, I~~~~~~~~

21 We will now elaborate some more on the properties of the coordinatizations just introduced. Proposition 2.2.3 A coordinatization of S is of type 1 iff for every ~HPS if C is a location of H, for some caD, then a is the only location of H. Proof We first show that if S is of type 1 (i.e. H t IUD O% = I, V~taD) and a is a location of H, then a is the only location of H. Clearly H i I, for I has the unique location ~. Suppose L # Ot is a location of H. Since (cL, L ' D-t and IL < H L C D-c t 4HD-ot <H L and H =U D-a U L = I. But 11 < 11 II < O u This in turn implies that H = I which is a contradiction to our assumption. We now show that if for every H on S, s.t. a is a location of H, for some acD, a is its unique location, S is of type 1, i.e. that T ULD-" = I, for all caD. Suppose this is not so. Then 3 aeD, s.t. H UH I. H < H UH andH < H U. This clearly imD- a a D-a D- a D- This clearly im plies that a contains a location of H U HD- and so does D-a. Since cY D-c a U H D-~ I, a is a location itself. Thus a and L are distinct locations of H U HD-_' where L is some subset of D-a. This contradicts our assumption. Hence S is of type 1. [II Proposition 2.2.3 proves that S is of type 1 if and only if all partitions with singleton locations have unique locations. We now proceed to show that S is of type 2 if and only if for any partition on S, no two of its locations are disjoint.

22 Proposition 2.2.4 A coordinatization of S is of type 2 iff for every HdP, if L and L2 are any distinct locations of H, then L n L i q. Proof We first prove that if S is of type 2 (i.e. for any D1,D2 C D with D n0 D2 = H, r I U D = I) and if H is any partition on S with more than one location, then for any two distinct locations L1 and L2 of H, L1 f L2 2$. Clearly H11 I, since I has the unique location c. Suppose L 0 L = 2. Since L1, L2 are locations of H1, HL U IL K H. 1 2 But by our assumption IiL U L = I, which implies H = I. This however is a contradiction. Secondly we show that if for any H with more than one location, intersection of any two of its locations is nonempty, then for all D1,D s.t. D 2 = D, HDIJ D2 =I, i.e. that S is of type 2. Suppose not. Then 3 D1,D2 s.t. D1 0 D2 = n, but HD1 U H D I. Let DI D2 H1 = HD U lHD. Then D1 contains a location of 1H, say L1, and D2 contains a location of H, say L2. L1 and L2 are different from c, since H $ I. D1 n D2 = ~ =; L1 n L2 = C. This however is a contradiction. Thus S is of type 2, which was to be proved. The next two types of coordinatizations are motivated graphically. These are coordinatizations with extension ropert2 (e.p.) and strong extension property (s.e.p.) defined below. Definition 2.2.7 Let {S j [i)D} be a coordinatization of S, where {(X,c,...I is the total ordering of D. S is said to have

23 a) e.p. if for all x,yeS and any i{1,...,n} if xHa y, then x(oL.) for j < i w,zES, where w(a ) = and (y(acj) for j > i y( j) for j ~ i z(a.) = J) = x( aj) for j > i b) s.e.p. if S has e.p. for all permutations of D. X Every set S with e.p. has a graphical representation G(S) by a multi-level graph. G(S) is obtained in the following manner. The set of vertices V equals U St, where all S are treated as distinct. Every coi.D i i edge of G(S) represents a subset of S X S, for some 1 < i < n-l, N1 i+l where n is the cardinality of the index set D. There is an edge joining (s, sa ) in G(S) just in case there is a point in S with the proi i+1 jection onto i'c i+, } equal to (sU3,s ). Every point s of S is thus represented by a path (s,sa,...,sa ) of the graph. It is clear from 1 n its description that this representation is one-to-one. Thus given G(S) of the type as above we can determine S uniquely. To make the representation more readable we will align the vertices along vertical lines. This is illustrated by Figure 2.2.3. Remark Every set S coordinatized over an index set D with JD I = 2, has a one-to-one graphical representation G(S). This is so, because every such S has e.p. We note that the above type of graphical representation does not provide a one-to-one map of sets without e.p. Looking at G(S) we cannot "retrieve" S, but only its closure with respect to e.p. By

24 the closure of Sw.r.t. e.p. we mean the smallest subset X of XS, aED such that X;S and X has e.p. It can be easily verified that the above closure is unique. We will say that a coordinate aeD is independent of the coordinates D' C D-a on S if 1IDi' H ll. a is independent on S then, if it is independent of coordinates (D-c) on S. For sets with e.p. "local independence" implies independence. This is stated more formally below. Proposition 2.2.5 Let S have e.p. and let {ca,cx2,...an} be the ordering of D. Then S is independent iff ai is independent of its neighbors, for i = 1,...,n, where the neighbors of a. are e. and H if 1 1-1 i+1 2 < i < n-l, and the neighbors of al are a2 and a and of a, ca and - n n n-1 ax. Proof If a~ is independent on S, then it is clearly independent of its neighbors. We need to prove the implication the other way. Let it(2,...,n-l). ai independent of its neighbors 7=> 3 x,yES with xa = ya and 1-1 1-1 xai =Yai but xa ya. But then 3 z,wES s.t. zk = W for k # i, where z = w x = Y and z = w = x {- 1 i- 1 -1 i- l 1i+ 1 i+i 1 i+ 1 Y=y and z x(, wx Ycx' This follows from e.p. property of i+ 11 1 1 S. Thus ZD7i w but z T4 w, which implies independence of a. on S. The proof for al and cn follows in a similar way. n

25 We will now take a closer look at coordinatizations with s.e.p. First, we will establish some auxiliary results to be used later. Lemma 2.2.2 Let S C >S, where S has e.p. Then S has the property, that i-l 1i for any x,ycS, any i', if xia. y, then for any cj a) (x,x "''. 'x x,,y,...,yO ) ES 1 2 J -1 3 j+l n and b) ( Ya2,..Yay,Ya, a,...,x )eS hold ) (2,J-1 3 3+1 n {== for any two disjoint subsets of D = {al',..., an}, D' and D" s.t. ( x if o. ED' D' U D" = D and any point z s.t. z(Oi) = 1, zES. 1 if a. cD" 1t Proof Clearly if any z as above is in S, conditions a) and b) are met. We have to prove that if S has e.p. and a) and b) hold then any z as above is in S. Let x,y,t.a be such that xn y. 1 Let {foi 'ai ' '...'ik denote the coordinates of D at which z 1 2 k changes from x to y or y to x, ordered by order of D. W.l.o.g. assume z = x for all oi <, z = y for ao. < oi < a z = x for (ai. 1i i c i ( 2 1 1 aix ti < a < ai, etc. Then if a) and b) hold, x[ y =Y z = ail a tai a. a ai 2 ll1. 11+n (x..,x,y,..,y,x,. '., X ) S. Again z ) - Y z ai m1 i -i 1 i n fl1 -1 2 2- 3 n Finally Zk = zS, which was to be proved.i

26 Lemma 2.2. 3 S C ~S has s.e.p, iff for any x,yES, any ai.D, if xla y, then i-1l i 1 for any c ejD a) (x l.x,a X, yj,xa Y...e*Y ) S 2 j-1 j+1 n and b) (y a,y,...y,y*,x,. ) S hold. 1 - j j+l n Proof I. If S has s.e.p. then S has e.p. for all permutations of D. If a. = a. (i.e. j=i-l) both a) and b) hold since S has e.p. and J 1-1 x = x = y = y~, same is true for O. = c.. j+1 1ai 61 cj+1 1 1) We assume that j < i- 1. We permute the oi. and a+ coordinates, denoting so permuted S by 1 ej+1 (x,xa,...,x *x, x,x,...,x,x *.,x ) ES l j-1 J j+1 j+2 1 i+1 n Then (xa,,X a2' * * x,x,x,x * *,... x 5ai Y++l1 * *)Sa)ES t(xy,y,x,yx,y,.,.,,,x ).ES ( 1 2 J-1 J 1 j+2 j+1 1i+ n (Y 3, Y. Y 3Ye,Y,,Y )~S (+Y i 1 2J-1 1 j+2 j+l i+ n But since S has s.e.p. S has e.p. and thus 2+2~~ n~~(aj+l OL al t I a2 j+l i+l n

27 (X 3X 2...,x j1,x,Y,Y,...y,y...,*y, )eS w(hxil J- *l j j+1 j+2 i i+ 1 n which -> (Ye Y2 ' 'Ycz, x,.x,.x,x, x,X0)ES 1 -ls~a2' slj ' aj+l j+2 i i+l n Thus a) and b) hold for any j < i - 1, if S has s.e.p. 2) for j > i - 1, we proceed in an analogous way, except that we permute coordinates (otiotj) rather than (ct j+l, i). II. We now prove that if for any x,yES and any a.ED with xll y, a) and 1 (1 b) of Lemma 2.2.3 hold for any aj # ai' then S has s.e.p. Suppose this is not the case. Then 3 a permutation of D, p, such that SP does not have e.p. That is 3 xP,yPESP and an a.ED, s.t. xPH yP, i.e. 1 a, (Xp))e*X ),...x )pyp )(Yp(i ) y 'Y (ot * but P(d,) (0 i) P( P (ai) P(d P(!i), P(n) either zP = ((C1) (o)Y p(ai)'..p() )S or wP = (Yp ( ) '...'Yp(ei)p(* i+ L)X...X p (n ))sP W.l.o.g. we assume that zPISP. We note that zP4SP = zgS, where x if zp =x (Ii 1_ (1 z = (z and = (z~i i Y if zp1 ) = Yi i P- (1i xPHl yP = xll. y. z4S =- a) or b) do not hold for some a., by Lemma N 1 J 2.2.2. This however contradicts our assumption. For the illustration of the proof we refer the reader to Figure 2.2.4. In the next proposition we prove that a set S with e.p. has s.e.p. if and only if it has e.p. under all cycle permutations of D, or, alternatively, if and only if it has e.p. under all transpositions of D.

28 C(S) 0 ___0__ 2 2 2 S = {(0, o, 0),,01), (2, 0,0), (2, 0,1), (,1,1), (2,2, 1)} Figure 2.2.3: A Graphical Representation of S. -1 "2 a3 a4 a5 a6 xII y x,yeS imply z,WES a3 Figure 2.2.4: Properties of S with S.E.P.

29 Proposition 2.2.6 Let S have e.p., where S C Sa and D = {a 1'an} 'nI. Then S i=l i has s.e.p. a) iff S has e.p. for every transposition of D b) iff S has e.p. for every cycle permutation of D. Proof a) Clearly if S has s.e.p. then for all transpositions t of D, St has e.p. We want to show then that if for all transpositions t of D, St has e.p., then S has s.e.p. By Lemma 2.2.3 to show that S has s.e.p. we just need to show that if xll y, then for any o. # acil (x,...,x*,yx,...,y, ) and (y. Ya',X ',.. 'Xx ) are in S. -1 3 aj+l n The proof of this however is exactly the same as the proof of I in Lemma 2.2.3, since only transposition type of permutations were used in the proof. b) We just need to show that if S has e.p. and SC has e.p., for every cycle c of D, then S has s.e.p. Equivalently, we need to show that for every x,yeS, any aiED, where xH y, (x,...,x,y~,...,yx )ES i. ~j j+1 n and (yo,...,y,xa,...,x )eS, for any aj.D. 1 j+l n 1) We first show that for any x,yES with xHl y, any point z s.t. z(ti) Y((i) or z(ci) = x(Oi), z is in S. Let ck denote the cycle of D with Ol in k'th position, i.e. cl ={c l,O2,.. 'n-, n} and for k > 2, Ck = {n-k+2'an-k+3''' '~n'l a2 '''n-k+l }' There are n cycles of D = {cl,.,cd}. Let { * {ail. '.i ''' } be ordered by the order of D,

30 where those are the points of change of z from x to y or y to x. W.l.o.g. take z = (x,' X,..,* xa,._.. x I, ) 3 i a (.2 j-1 1-1 i i, i-I, 12 2 3 3 Consider ce, where L = (n+l)-(i -1) = n+2-i, i e. L = n+2-i,, ci Cc Cl Cl Cl m=l,.,k. Now xES,yES — > x IS and y is 1, ie. (x,X,...,x, X,.,...x )ES and 1 +1 1 2 11 n n (Y1 2Y.2 1(Y1 clearly implies that z= (x,l,x 1 Ix. Y (Y. ) i ' 1 2 1-1 1+1 n 1 1 1 where z l= Ya for all a. > a. Z 2~S 2 and z 2 = (Z,z z,z ',z '.z ), i.e. z 2= (y,y,Y S...y..Yx x,...,x,y s ) ES,.,y 1 ai a(+ an a1 a2 a a. a ai 1 C' C (xi ti +1 an) 2 i-1 ia i2 i i+ 1 1 l 1 hra a a a a for al. a t..2 2 n 1 21 = a1 a2 a 1 ( a ai+1 a. a. i +1 ai 2 al U2 -ISU and +I (xiz-1- 1,, 1,z I 1 2 2 2 n,roceeding this way we show that z.S. J,,yT )eS ~

31 w =(,... x,y..,y ) and p = (yl,ya...,y x...x ). O1 a aj+ant t 2 nj tj+1 n are in S. It suffices to show that weS, since the proof for p is analogous. Let c be a ((n+2)-i)'th cycle, i.e. c = {ai,ai+...,a...,ti- } (i > 2, since for i = 1 the assertion was proven). To show that wES it suffices to show that wCESc. We note that xC and C c c y are related by first coordinate in SC. Also SC has e.p. and so do all cycle type of permutations of c. Thus by part 1) wCESc, which implies w S. The proof of 2) is illustrated by Figure 2.2.5. U 2.3 Relations among Coordinatizations In this section we will analyze the spectrum of coordinatizations. The levels of the spectrum will be numbered I through VI and we will prove that if coordinatization is of level j, then it is also of level i, for any i smaller than j, provided coordinatization has no constant coordinates. The case of coordinatization with constant coordinates will be discussed separately. We will also provide and prove some sufficient conditions, under which the implication goes from lower to higher levels. The spectrum of coordinatizations is shown in Figure 2.3.1. Theorem 2.3.1 Let S C XS be a set with no constant coordinates. Then if cooaCD ordinatization of S is of level j in the spectrum of coordinatizations, for any 2 < j < 6, it is also of level j - 1.

32 x,yE:S,x y implies (x,x2,x,x 4, 5 Y6)S al a2 a3 a4a as a6 3 a, a 26 3 4 6 c Y6 x "4 ~x a a2 2 a y ac = (3,4,,c6,c1,2) c 1 a Y56xa'~l xaCc2 c ~~ a3 a4 a5 a6 a1 a2 " ya z = (X;x, x x,y,y u3 4 a3. a4a3 a69 al a2 a3 a 4 a5 46 Figure 2.2.5: S Has E.P. and SC Has E.P. for Any Cycle c.

33 Proof a) j = 6. By Proposition 2.2.1 S is irredundant and hence of level j - 1 = 5. b) j = 5. S is irredundant, which implies that every IePS, 1 $ I, has a unique location L1 I. Thus QL1 = LL - L and S is of level LzL j - 1 = 4 in the spectrum (i.e. of type 3). c) j = 4, i.e. S is of type 3. Let H be any partition on S with more than one location. Let L1 # L2 be any two locations of H. Then clearly since intersection of all locations of ii is nonempty, so is Ll n L2. By Proposition 2.2.4 this implies that S is of type 2, i.e. level III in the spectrum. d) j = 3. Clearly if for all D1,D2 C D with D1 n D2 = D, HD U H = I then Hla U HIDD = I for Vo eD. This is true because D1 D2 c D-c 01 n(D-a) = P (we note that IDI was assumed to be >_2). Thus if S is of level III in the spectrum it is also of level II. e) j = 2, i.e. S has the property that IIo U HD-I = I, for all OaED. Since S has no constant coordinates, Ho # I and thus a is a location of H a. By Proposition 2.2.3 this implies that at is the unique location of lHa, for all acD. Finally, by part a) of Theorem 2.2.2 this implies that S is independent, and thus of level I in the spectrum of coordinatizations. E We will now show that all levels of the spectrum are distinct (in general). For every level we will exhibit a coordinatization, which is of this level, but not of level one higher. Theorem 2.3.2 For every j, 1 < j < 5, there exists a coordinatized S s.t. S is

34 aED I i Independent, for V aED, [D-( \ c II | Type 1, for Vc aED, 1U %IIDa = I III | Type 2, for V D1,D2 C D, with D1 n D2 =, DD U D =I IV Type 3, for V lPSF, ii # ICL #,, where LEL L is the family of all locations of H. V Irredundant, for V llpS, H I has a unique location VI Cartesian, (S) Figure 2.3.1: Spectrum of Coordinatizations (No Constant Coordinates).

35 of level j, but not of level j + 1. Proof a) I > II Consider S = {(a l,b l),(a2,b),(a3,b 2),(a3,b 3)}. Clearly S is independent. With D = {cl.d2} we note that D_ U J = 11 U =DC2 2 a1 a2 (ab ), (a2), (a,b ),(a3,b3) U =(ab),(a,b ) (a b), (a,b4= {(albl),(a b ), (a,b ),(a3,b3)t I b) II #> III Consider S = {(al,b,c,d ), (ab,cd ), (a,b,c,d ), (a,b,c,d ), (al,bl,C2,dl), (al,bl,cl,d2) } It is easy to show that a1U a. = I 2U a aF U HDa = However the partition 1 = (a,b 1,cldl), (al,b 1,c2,d 1),(al,bl,cl,d2),(a2blc,d ),(a,b,c,d ), (a2,b2,c2,d2) } has locations {al,a } and {a3,a4}, which are disjoint. Thus by Proposition 2.2.4 S is not of type 2 and hence not of level III in the spectrum. c) III #> IV Consider S = {(a,b,c),(a,e,c),(d,b,f),(d,e,c),(a,e,f)}, D = {al,a2,a3}.

36 We first show that S is of level III, i.e. that for all D,D C D with D1 n D2 = A' TD U lD = I. Actually to show that it suffices to show that for all D1,D C D with D1n D2 = ~ and D1 U D2 = D, ID U D = I 1 2 — D2qandD1UD 1 12D D 2 Thus we need to show that 1H UII =, II, (n U = I and EL UI 1 U I. This howl1 2" ~o3 ~ 2 C1:U c3 3 1U ever follows easily by inspection. Let 11 = l (db,f), (a,b,c),(a,e,c),(d,e,c),(a,e,f)}. It can be verified that {l, },{cal,c3 } and {2,13 } are locations of I. Obviously {a1,a2} n {al,a3} n {a2,a3} =. Thus S is not of level IV. d) IV #> V Let S = {(a,b,c),(a,e,c),(d,b,f),(d,e,f),(a,e,f)}. We first prove that S is of level IV, i.e. for any partition H on S with more than one location, intersection of all its locations is nonempty. Since IDI = 3 however, to prove that, it suffices to show that for any D1,D2 C D s.t. D0 n D2 =, 11D U HD = I, i.e. that no two distinct locations of II 1 2 are disjoint. (For then no H can have more than two locations.) To prove that, it suffices to show that {o.{ ~2 C3= I U {} I and a I, 11c { } = I, which a1 {2 13 2 1 3 3 1 Jl2 clearly holds. S is not irredundant, for example T = {(a,b,c), (a,e,c),(d,b,f),(d,e,f),(a,e,f)I has two locations {al,a2} and {(12,a3 } e) V 74 VI Consider S = {(0,0),(l,0),(1,0),(1,1)}. S is irredundant but not Cartesian, since (O,1)S. C

37 Remark For S with constant coordinates and any 3 <j < 6, if S is of level j then it is of level (j-l). If coordinatization of S is of level II however, then every tacD is either independent or constant. Thus II # I. The above can be easily verified by tracing through the proof of Theorem 2.3.1. We shall now give some conditions under which the implication in the spectrum goes from a lower to a higher level. We note that if cardinality of an index set is two, levels II, III, IV and V are all equivalent. Also as was pointed out in part d) of the proof of Theorem 2.3.2, if IDI = 3, then levels III and IV are equivalent. Other conditions are stated and proved below. Proposition 2.3.1 Let S be independent. Then S is irredundant if either a) or b) holds, where a) H = {TilITPS and I1 has a unique location} is a sublattice of P S b) PD ={l SI ID' CI D} is a sublattice of PS. Proof 1) We prove that if a) holds, S is irredundant. We need to show S _< S S that for any D1,D2 C_ D, 0Dl D2 - D 1 2 2r) D 1 D"2 Since S is independent, by part b) of Theorem 2.2.2 ND has a unique location D1 and DII a unique location D. Since a) holds n = ND U HD has a unique location, say L. Since ~ < II and ND ~<, D1 -- L and D D L. Thus D1 n D2 D L. This implies that IID < nH But L being 2 -' —',f~D, L'

38 the location of i implies ]L _< H. Thus %1/D_ < %, 2) We prove that if b) holds S is irredundant. Again we need to S S show that ln D2 <- U HD 2 Since PD is a sublattice of pS, D U D2 =, for some D C D. iow D < IDt U D2 = Dand HD <ED H. Since S is independent, D3 is the unique location of "D3 2 3 Thus D1 m D3 and D2 D D3, which — > D1 n D2 2 D3. But this in turn implies that inD2 %3 =%U 2 1 2 3 1 2 As was stated in Proposition 2.2.2 cardinality of an independent set S is at least one larger than the cardinality of its index set. If those two are equal, i.e. if ISI = IDI + 1 we will refer to S as a minimal independent set. We will prove in the next proposition that every minimal independent set is also irredundant. First we will state and prove an auxiliary lemma. Lemma 2.3.1 Let S be an independent subset of X S, where IDI = n and IS = n+l. Then 3 an enumeration of D, {.,O'i,' ' ', } and an enumeration 1 2 n of S, {so,sl,..,sn } with the following property. For Yi, i=l,...,n, defined recursively by Y1 = {so,s }, and Y. = Y. U {si} for i=2,...,n, S! So and for every sg, where 2 < <n, 3 an sEYel s.t. I D-a. t 1D Proof Pick any acD and let a. = a. Then since coordinate ai. is independent on S, 3 s0,s lS s.t. S ODy s. (Of course pic s. ) Let Y1 = {sW,sl}' We now show that 3 a BSED-oli. and an s BS-Y1 s.t. ll

39 SaHD- so or S %D-S. This is true for the following reason. All coordinates of D-a. are independent. So for every yED-a. 3 s,zyES s.t. SynD-yZY (while s J<z ). Now s = so and z = s cannot hold for any ~yED-., since ct. D-y and so0Ha sl. If for no yED-aci 31 a z ES-Y i1 s.t. Z DsO or z D- s, all coordinates of (D-ai ) are independent on S-YI. Since ID-oi I=n-l, this implies by Proposition 2.2.2 that IS-Yll > (n-l)+l=n, which implies that ISI = IS-YlI+IYll > n+2. This however is a contradiction to ISI = n + 1. So 3 a BED-Oa and s ES-Y s.t. S HD_ s or S 8DS1. Let ai. = s2 = s and Y = Y1 U {s }. We then show that H a yED-{.c cti I and an s YS-Y2 s.t. s HD-ys 1 i2 y y o or S Dy S1 or Sy HDyS2 holds. In an analogous manner we prove at the k'th stage that 3 a yED-{a.,... t } and an s YS-Yk s.t. s -yZ -l 'ik ~' for some zcYk. 0 We will now illustrate Lemma 2.3.1 by an example. Example 2.3.1 Consider S = {(0,0,0,0), (0,0,0,1), (0,1,0,1), (0,0,1,1), (1,1,0,1)}, where D = {tal,o2, 3,c4}., S is clearly independent and ISI = IDI+l = 5. We demonstrate one enumeration of D and S, as of Lemma 2.3.1. Let so = (0,0,0,1), s = (0,1,0,1), s2 = (0,0,1,1), s3 = (1,1,0,1), S4 = (0,0,0,0). a = %, 'a = a3, = a and a. =. Thus Y - (1~ll 1 2 3 W1 4 1 {(0,0,0,1), (0,1,0,1)}, Y2 = {(0,0,0,1) (0,1,0,1), (0,0,1,1)}, Y3 = {(0,0,0,1), (0,1,0,1), (0,0,1,1), (1,1,0,1)}. We verify that soH D sl, s2HD-a3s O S 3HDa S1 and s4 DHa s. Hence the enumeration is as desired. Proposition 2.3.2 Let S be an independent subset of X<S, where I DI = n(n>2) and

40 ISI = n + 1. Then S is irredundant. Proof We proceed by induction on n. a) induction base We show that for n = 2 = I {a1, a2c} and S = {s0,s,s 2 } if S is independent then it is irredundant. For S independent either 1) sOHa sL, sla s.2 or 2) sOHal sl, s0H s2 or 3) sOcla s2, sO a sl or 4) sO1a s2, 2 1 2 o 2 1 slHa2s2 or 5) sila s2 s Oa s or 6) sl s2, s2Ha so holds. In all 2 2 1 2 those cases S is irredundant. b) induction step (*) We assume that if IDI = k and S is any independent set coordinatized over D, with ISI = k + 1, then S is irredundant. We want to prove that if IDI = k + 1 and S is any independent set coordinatized over D, with ISI = k + 2, (*) => that S is irredundant. Let S = {sO,sl,...s skSk+l} be an enumeration of S and {I,ai,... ai k,.i } an enumeration of D as in Lemma 2.3.1. [: k2 i k+i S = Yk U {sk+ }, where Yk = {sO,,' s k}. The coordinates {a,...,ai are all independent on Yk' since for every St, 1 < l _< k, 3 an sEYk s.t. S HDa s and sg ~ s. We also note that coordinate a. is constant on 1 k+i Yk' This follows, since slD_-. sO Pa. (Sl) = Pa. (s0)' S2 D-x.s1 i 1ik+l 'k+i 12 or s2 SD_ s0 => Pa (s2) = P (s1) (or pa (sO)), etc. Let Yk i2 k+1 k+ kk+ 1 denote the projection of Yk onto D = D-k+, i.e. Y= P (Yk) ik+ ' Then since Yk is independent, IYk = k + 1 and JDJ = k, by (*) Y is irredundant. This implies (trivially) irredundance of Yk.

We now need to prove irredundance of S. We have to slhow that for S S S any zEYk any D1)1,D2 C D, if Sk+lD z, then Sk D D z. Let 1' 2 1 2 Z'D1 D be as above. Since 4T 5k+' S. JD nD 2 W. 1. o.g. assume 'i ' k+' ik+1 k+k 1 that ca. iD1, i.e. D1( D-ai. Now Sk+l s, for some sYk k' k+1i 'k+1 (by construction of Yk's). Since D1 C D-t., this implies that Zk+1 S. Since S k Since k+. nD DZ and sgD S+(for DknD2 C D), S Y S11D D z holds. Hence clearly s D nD z. Since Yk is irredundant, 2 1 2 k S(k U 'D )z and so s( l U )z. Since Sk+1, Sk+l ) 1 2 1 2 1 2 So s(4 U l )z, which completes the proof. (We note that this proof 1 2 works for Di r D2 =.) I Example 2.3.2 Let S = X Sa, where IS I > 2 and IDI = n. We construct a subset X of S in the following way. We pick any S1 S. Let s2 be any point of S s.t. P (s2) # P (s,) and PD (s ) = P D-(sl), let s3 be any point of S s.t. Pa (S3) # Pa (s2) and PDo (s3) PD- (S2)' etc. That is 0/,2 2 O~2 2 Si is any point of S s.t. P (si) = P (si.) and PD-a (si) i- -1 - 1 i-1 PD-a (Si ), for 2 < i _< n + 1. IXI = n + 1 and X is clearly indei-1 pendent by construction. Hence it is irredundant by Proposition 2.3.2. For S = {0,1}5 the following set X (constructed as above) is irredundant.

42 {( 0, o, 0, o, o )} UJ U( 1, 1, o, o, o )} U {( 1, 1 0, )} {(, i, i, i, 1,i)). a We will next show that if S is of level II and has strong extension property then it is Cartesian, in case the cardinality of an index set is greater than or equal to three. Proposition 2.3.3 Let S CXS s, where IDI > 3 and S has s.e.p. Then if S is of acD level II (type 1) it is Cartesian. Proof First we note that if S is of type 1, I t U IID = I for all o~D. This implies that for any oa,BD, a # B, HII I = I on S. We will show that for any x.iPi(S), i=1,2,...,n, where IDI = n, (x1,X2,...,X n)S, provided H ( IJ HI = I, for all e, SzD(cx#S). So actually we will prove a somewhat stronger result than the one stated. To show that (x1,x2,...,Xn) S it suffices to show that for every i, 1 < i < n - 1, 3 some point si in S s.t. Pi(si) = xi and Pi+l(si) = xi+1. 1 1x1 1 i+1 1 This follows since S has s.e.p. and siIf si+l, where si's are as above. xiEPi(S), Xi+lx Pi+l(S) S 3 z-, wi+leS s.t. Pi(Zi) = x and Pi+(wi+l) = 1 1 zi+ i 1r 1 i+ p Y~ Sincel.U1i+l =Is S pIX***,peES s.t. ziwp ~ n IT i+l This implies that 3 a broken line from the point x. of G(S) (the graph 1

43 of S) to the point xi+1 of G(S). This line is composed of segments (PiPi+l), where piEMi(S) and pi+l.Pi+l(S). By the length of this line we will mean the number of segments it is composed of. We want to show that there is always a broken line of length 1 connecting xi and xi+l (for any i, i+l, any xi, xi+l). This will clearly imply that si s as defined before are in S. We note the length of the broken line is always odd, i.e. 1, 3, 5 etc. This is illustrated by Figure 2.3.2. We will proceed by induction on l, the length of the broken line connecting xi and xi+. We show that for any odd k, k > 1, if there is a broken line of length k from xi to xi+,, then H a broken line of length 1 from xi to xi+. a) induction base, for k = 1 this is obvious b) induction hypothesis. Let k be any odd number > 1. (*) We assume that if there is a broken line of length k connecting any two points piEPi(S) and Pi+l Pi+ (S), then HI a broken line of Z= 1 connecting Pi and Pi+l. We will show that (*) implies that for any xic Pi(S), any xi+lPi+. (S), if i a broken line of t = k + 2, then there is a broken line of l = 1 from xi to x i+. Let L be such a line, t(L) = k + 2. Then let yi+ denote a point on L s. t y Pi+ 1P (S) and 1+' i+l 1+1 Z(L(yi+,xi+l)) = 2. L(y i+,xi+ ) denotes the segment of L between i+ andi+ and Z(L(yi+ lxi+ )) its length. Then Z(L(xi,yi+l )) = k and thus by (*) 3 a line segment L(xi,yi+l) s.t. ~(L(xi,yi+l )) = 1. Let L be a broken line between xi and xi+ defined by L(xiY ) = L and L(Yi+lxi+l) Clearly L(L) 1 + 2 = 3. Let yiEPi(S) denote the point of L, s.t. Z(L(y~,xi+.)) = 1,

44 I I I 1 x. x( 1 I 1 1 I I I 1 I I I x. I I I I I Xi+ I + xi +l i-i i i+l i+2 i-i i+l i+2 i-i i i+l i+2 k=l k=3 k=5 a) b) c) Figure 2.3.2: Broken Lines of Length k Connecting x. and x.+l........__~ _~ 1 i+l 1. - \ f ~1 '' I Yi dw~~~~S +1 ri+2 \~~~~ % i+l Pi+2 i i+l i+2 Figure 2.3.3: Illustration of the Proof of Proposition 2.3.2.

45 i.e. (y_,xil ) is the last segment of L. We assume that i + 1 < n - 1. Then a a piS s.t. p Y i+ Xi+l 2 Pi+2 +2 Also rES.t ri = Yi and ri+l = Yi+l Since p iir and S has s.e. p. H a t S s.t. ti = Yi, t = Yi+ and t = P+. Also since (xi,yi+l) is a seg1 1t+1 +: 1+2 1+2 i+1 ment of L, 3 an htL s.t. hi = xi and hi+ = yi+ hi+ t holds, which implies that a a ueS s.t. ui = xi, ui+l Yi+l and Ui+2 = Pi+2 i i i Now ui+ p - a a s ES s.t. si = x. and Si = Xi+l Thus a a length-l 12 i+ 1 1i+ 1 segment connecting xi and x i+ In case i + 1 = n, we use (i-l)'th coordinate as an auxiliary one (rather than (i+2)'th coordinate) and proceed in an analogous way. The proof is illustrated by Figure 2.3.3. 1 2.4 Theory of Irredundance In this section we will discuss ways of obtaining irredundant sets from other sets, for instance those which are known to be irredundant. We will start by pointing out a graphical interpretation of irredundance for sets coordinatized over an index set with cardinality two. Proposition 2.4.1 Let S C S X S. Then S is irredundant iff for any two points 1 2 plp2EG(S), a a path connecting p1 and P2. Proof We first point out that any S as above has e.p. and so G(S) is well defined. S is irredundant — )S U S = I <(-> for any two points 1 (2 c' 1 a2x l ~ zk s. L II ZkTIZ Y ~ —for any P1,P2 G(S), a a path connecting P1 and P2. 0

46 Example 2.4.1 Consider S1,S2 CS X S, where S = {0,1,2} = S and 1 2 1 S1 = {(0,0),(0,2),(1,0),,(2,2)}, S2 {(0,0),(1,0),(1,1),(2,2)}. Then (refer to Figure 2.4.1) S1 is irredundant but S2 is not. M1 We will now prove that if S is irredundant then its projection onto any subset of an index set is also irredundant. Proposition 2.4.2 Let S C XS be irredundant and let D be any subset of D. Then OtED P-(S) is an irredundant subset of XS DED Proof Suppose S = P-(S) is not irredundant. Then a a partition II on S with more than one location. Let L1,L2 be two distinct locations of I. We will show that then 3 a HI on S s.t. L1,L2 are locations of H. Let II on S be defined by xly <= — P?(x) HP=(y). 11 is well defined and we show that IIL < 11, IHL <. 1 2 Let xll y, where x,yES. Then P5(x)lSl P-5(y), since L1 C D. But D 1 ll < 11 -> P-(x)lP-~(y) => xTly. Similarly 2L H< I. We now show that for any L C D, if HTL < 11 then. Let xlL, where x, yS. = P (X), y = P-(Y) for some x,yES. Clearly xLy holds. Since t _ H, xlhy. This => P-(x)IiP-(y), i.e. xHy. So L1 and L2 are locations of HI. (L1,L2 both contain locations of H, but by the above argument this containment cannot be proper.) Thus S is not irredundant, which contradicts our assumption. E We will now show that a Cartesian product of a finite family of

47 sets is irredundant iff all the sets in the family are irredundant. Proposition 2.4.3 Let Si CX S ' for i=l,...,n, where Di D = ( for i # j. 1 Then S = <Si is an irredundant subset of > S (>KSa) iff si is an iri=l z=1 alDD 1 redundant subset of X S for il,...,n. Proof a) Since Si = PD (S), clearly if S is irredundant so are all S (by Proposition 2.4.2). b) We now prove that if all Si are irredundant, then so is S. We will prove it for n = 2 case, since this can be easily generalized by induction. Let S1,S2 be given, where SS2 are irredundant, S = S' X S2. We need to show that nD z_ NL 0 ll, for every D,D C D, where D = D1 UD2. Let D1 = D n D1 and D2 = D n D2. Similarly let D = D n D, and D = D n D. Clearly D = D1J D2, D = D1 UD2, where 1 2 1 2 12 2 D1 D' = (, D1 2D = = 11. D2 = ( and D2OD1= (. Thus D = (D n Dl) U (D2 n D2), andU (D22) 2) = D (B 1q D,) uJ (BDn2'D2) S H(n~r ) f 2o-2. We will denote any point xES by (xl,x2), where X ES1 and X2ES2 are such that xl= PD (x) and x2 = PD (x). Let 1 2 X[n l y This implies xl I y1D and x2 yn. Since S1 are 2 2 irreduS 1 andant 2 s.t. 1ISI 1 21 SS2i 2 S 2 S2 x1inz Rzl, Zl..., Z11H, -y1 and x2%D w2 w2..,II 7 n' 2 y2. Let 1 1 1 2 2 2 2 m = max(k,~). W.l.o.g. we assume < k and set wt+l =,+2 = = k S1 2 =(xx S 1 2 D(1 2 )U 1'w)' By similar 1 2 argument it is clear that 5 '11S 22 k S (x1CI~ ~D 1w,/ILD, UD2 1 (z,w2)H - (yy ), i.e. 2DDD D 2 D2 1 2 D2UD2

48 Sj S S S ii S S xDI p k P2...pky, where p (z1,w2). So X(HI U.)y, which was to be proved. [D Proposition 2.4.3 is illustrated in Figure 2.4.2. In general, union of pairwise nondisjoint family of irredundant sets is not irredundant. This is shown in the example below. We will state the conditions under which such a union is irredundant. Example 2.4.2 Let S1 = {(0,0,0),(1,0,0),(1,1,0),(1,1,1)}. S1 is of the form of Example 2.3.2 and so is irredundant. Let S = {(0,1,1),(1,1,1)}. S2 is obviously irredundant. S1 in S2 = {(1,1,1)} l. S = S1 S2= {(0,0,0), (1,0,0),(1,1,0),(1,1,1),(0,1,1)} however is not irredundant. Consider a partition on S with two equivalence classes, 1 = {(O,1,1), S-{(Ol,l) }}. Then L1 = { l,t2} and L2 = {(l,a3} are both locations of R. E Proposition 2.4.4 Let F be a family of irredundant subsets of XS s.t. OLED S ')S S 4, for any S,SeF. Then X = JS is irredundant if S EF a) for any S,ScF any sES, any SES and any L C D, if sIls, then 3 a point pcS n S s.t. pHlls. Proof We need to show that for any D1,D2 CD, 11ND < U TD. Let D1,D2 be given and let x,y be arbitrary points of X s.t. x1NDay Then xeS,yeS for some S,SEF. If S = S the above clearly holds, since S is irredundant. So assume S # S. Then by condition a)

49 0 0 0 0 1 t" f1 1 1 2 2 2 2 G(S1) G(S2) Figure 2.4.1: Graphical Interpretation of Irredundance. 00 0 0 0 0 1Y Y1 81 t 1 1 t I al c 2 a2 1 22 G(S1) G(S2) G(S S2) S = {(0,0),(0,1),(1,0)} S2 = {(0,0),(1,0),(1,1)} 1 2 Sx S2 = {(O,0,0,0),(0,0,1,0), (0,0,1,1), (0,1,0,0), (0,1,1,0), (0,1,1,1), (1,0,0,0), (1,0,1,0), (1,0,1,1) } Figure 2.4.2: Irredundance of S,S Implies Irredundance of S1S2.

50 a a zSnl s.t D1 D2z and YHx z. (If D1 n D(2 =, then this DiD2Z andy D2 says simply x,zES and y,zES.) Now by irredundance of S and S this implies x(ll UID )z and y(ll U II )z. This clearly implies that 1 2 1 2 xC( U It )y, which was to be proved. a Remark The sufficient condition of Proposition 2.4.4 is not a necessary one. This is demonstrated by the example below. Example 2.4.3 Let X1 = {(al,bl),(a2,b1), (a2,b2)} and X2= {(al,b2), (a2,b2),(a3,b2)} be subsets of {a,a2,a3} X {bl,b2}. X1 and X2 are both irredundant and so is X = X1 U X2 (refer to Figure 2.4.3). X1 n X2 = {(a2,b2)} and although for (al,bl)EX1, (al,b2)EX2 (al,b1)Hl (al,b ), there is no point z in X1 n X2 s.t. (al,b1)l)lO. As a corollary to Proposition 2.4.4 we will now show that a union of a family of pairwise nondisjoint Cartesian sets is always irredundant. Corollary 2.4.1 Let T be a family of Cartesian subsets of XS with the property a D that for any C, C in Y, C ( mC # {. Then X = UC is an irredundant subset of XS. C EjTY c&D Proof We just need to show that condition a) of Proposition 2.4.4 is met. Let L C D and let xaC,yEC be such that xlly. We need to show that a a point zeC n C s.t. PL(z) = PL(X) = PL(Y) If L = ~ this is clear

51 for C OC n c. If L = D, x = yLcCyCC. So assume ~ f L C D. Since C n C # 4,: a point w~CnC. Let z be a point defined by x(ca) for aEL z(0) =. Since C is Cartesian and x,wcC,zFC. Since w(a) for EclD-L x(a) = y(a) for V~EL, and y,wcC,zcC. Thus zECnC and z is as required. In general, complements of irredundant sets are not necessarily irredundant, as is illustrated below. Complements of some irredundant sets however are always irredundant. The next few propositions will demonstrate types of irredundant sets, for which this is the case. Example 2.4.4 Let S = {al,a2,a3}2 and let X = {(a1,a ),(a,a2),(a2,a3),(a3,al),(a3,a2),(a3,a3)}. Then X = S - C {(a1,a3),(a2,a1),(a2,a2)}. X is irredundant while its complement is not. For the graphical interpretation refer to Figure 2.4.4. C: We will now prove that a complement of a Cartesian set is always irredundant (in general not Cartesian). Proposition 2.4.5 Let S = XS and let Y be a Cartesian subset of S. aEcD Then S-Y is irredundant. Proof Since Y is Cartesian, Y = Y S —Y = X S a Y = (S ) ac-D ED MPED CeD sE D = -Ys,for $ = c where S-. This can be easily shown by induc-; Sg ( 5, for s e tion on ID!. Let D = {clalcD & Y = S }. If D = D, then S = Y and

52 al b a1 _b a b 1 1 2a2 a2 a22 b2 2 3~a a33 a3 1 h2 1 Q2 "1 a2 X1 Figure 2.4.3: Irredundance of Union of Sets. a1 ~a a1 a1 a2 a2 a2 a2 a3 83 a a3 G(X) G(S-X) Figure 2.4.4: Irredundance of X Does Not Imply Irredundance of its Complement.

53 S-Y = J is vacuously irredundant. So assume D C D. Then for every ac XC S = o- Hence S-Y= UQ-) Now n XS)= XS,,eDt aeD-D BDe acD-D o cD aED (S for a~D where S = Sa # g, for V a. Thus S-Y is a union S, -Y for acD-D of a family of Cartesian sets with nonempty intersection and is irredundant by Corollary 2.4.1. [1 Remark Since every singleton is a Cartesian set, its complement is always irredundant. In other words removal of any point from a Cartesian set does not change its irredundance. n As was shown in Proposition 2.3.2 every minimal independent set is irredundant. We shall now prove that its complement is also irredundant. Proposition 2.4.6 Let S be Cartesian, S = XS, where JID = n. Let X be an indeaOD pendent subset of S with IXI = n+l. Then (S-X) is irredundant. Proof We will use induction on n(n- 2). 1) Induction base. n = 2 case. Let D = {a la2} and X = {x,x2,x 3}. Then 3 xa s.t. al is constant on X - {x} and its value on X - {x} is distinct from P (x). (This follows from the proof of Lemma 2.3.1.) W.l.o.g. we assume that x = x1. Thus P (x2) = P (x3) ~ P (xl). Also P (X) = P (x2) or Pa2 (xl) = P (x3) holds. W.l.o.g. assume

54 P(xl) = P (x2). x= {x} U {x2,x3} = {(x1,x2 ) } { } X {,x3 12 2 2 1c 2 c 2 c2 Thus S X S - {x2 })X (S _ 3 {X2 3X S Ot2 t2 (2 (1 1 {(x1, ) } = {x } X (S- {x2 }-{x3 }) U (S - {x I- {x }-{X X s 11 2 2 1 1 1 {x } X (S 2{x2 }). We note that S2 {x2 } - {x } { } C {ot2 2 - aa 2 ~~~~~~~~~~~1 2~2 2 2 and also that each of the three sets in the union is irredundant. Thus, U 11 = I holds on S-X and S-X is irredundant. 2) (*)We assume that for n = (_> 2) the proposition holds. We need to prove it holds then for n = Z+l. W.l.o.g. let D = {cl,a2,..., ','c+ } and X = {xl,x2,...+,xZ,xt x } be enumerations of D and X s.t. Po (xi)is constant for all i > 1 and P (x') Po (x ) for all i 4 1. (We know a Y and an x with this property do exist.) We also note that 3 an xJX - {xl} = {X2,x3,...,x2 } s.t. PD (xl) = P (xi), i.e. P (X 1) C 1 D-O -- PDa ({X2 x3 x+,3). S1 X 2 X... X S X S+1 - {Xl,X2,,X, } = {x. } 2 X... X S X St+ - {x1} U (s }) x s X... X S X S+ - {}2 3 = Z+1 I {X } x (S2 X. X S X S+1 Px a (XS) ) 21 2 1 (S{-{x })-{x2 }U {x2 }) x S2 X.. X St X S - {X2 } X PD{ }({x2,x3...,x }) = {x' } X (S2 X... X St+, -P (X1))U 1 1 ~ (S- ){)X X } X X S U {X } X (S X.. XS X S - P (X )) ax } (S2 l X+1 DO {... ) 1 2 3 (Y.ID1Ir

55 We note that Y1 is irredundant as a product of irredundant sets (by Proposition 2.4.5 and 2.4.3). Y2 is irredundant since it is Cartesian. Finally since the set X = P....,x }) is a minimal independent subset of S2 X... X Se+l, by the assumption (*), (S2 X... X S+1 - X) is irredundant. Thus by Proposition 2.4.3 Y is irredundant. Hence Y1, Y2' Y3 are all irredundant. We need to prove that so is their union. We need to show that for any x,yES-X, any D1,D2 C D s.t. xi 2nD2Y x( Di U D2 )y. If both x and y are in Yi, for some i, then x(Dl U D2 )y clearly holds, since V Yi are irredundant. Now if xEYi, ysYj, i t j, then ctlD1 r) D2. This is so, because P (Yi) P. (Yj) = for i # j. W.l.o.g. we assume that a1:tD2, i.e. that D2 C D-a1. We note that PD- a(Y) C P0_ (Y) C ()C PD(Y2) holds, so for any pair i,j, itj either P (Y~) C P (Y>) or P (Yj) C % (Y ) D —cl jl D-otD, Say, PD (Yi) C P (Yj) holds. Then for xY. 3 a zEYj s.t. P (x) = 0-ct1 _ D-et j 1 1 P I (z). But D2 C D-a => x% 2z => x(% tU % )z. Now zcY., yEY and Z. % nD x =- Z% nD y. But Yj is irredundant and so z(I% LJ ID )y. 1 2 1 2 1 2 This implies that x( % UJ % )y, which was to be proved. n We will next prove that a complement of an arbitrary subset of a Cartesian set, all of whose coordinate projections are properly contained in corresponding coordinate projections of a Cartesian set, is irredundant. Further we will show that every superset of such a complement is irredundant. First we will prove an auxiliary lemma.

56 Lemma 2.4.1 Let S =XS, where IS I >_ 2 for all acD. Let C C S, where acD C = XCC and Ca; Sa. Then any set Y D S-C is irredundant. Proof Let X = S-C. Then by Proposition 2.4.5 X is irredundant. We will assume then that Y? S-C. We will now show that for every zEC, every aXED, J an x EXs.t. z 11 x. Let aa c Sa- Ca. Then =(zX I zc1,a $z a. z) cX, for a C Obviously xlD z. We need to show that for any x,yaY any D1,D2 C D, if xY YnDY, then x( L II )Y. Now if D = D, D1 = ~, D2 = D or D2= the above clearly holds. So assume c # D1 # D, c D D2 # D. Let x,ycY be as above. Then 3 z,wEX s.t. xl z, yl w. If xEX take z = x, if yeX, take w = y. Since 1 1 X = S-C, if xEY-X, then xCC. But we showed before that then 3 a point z X s.t. zlD x. (Note that D1 C D-c for some acD.) The same holds for yEY-X. Since X is irredundant and w flnD Z) w(l U )z. Thus x(EI U I, )y, which we set to prove. For an illustration of this proof refer to Figure 2.4.5. D Corollary 2.4.2 Let S = XS, where IScl 2 2 for V cED. Let Y be an arbitrary aE:D subset of S with the property, that P (Y) $ Sc, for all aED. Then every set X s.t. X D S-Y is irredundant.

57 Proof Clearly Y C XP (Y) and so S-Y D S - X>P((Y). Every superset of wcD aE)D S-Y is clearly a superset of S - XP (Y) and so is irredundant by uED Lemma 2.4.1. We will illustrate the above corollary by an example. Example 2.4.5 1) Let S = {0,1,2}2. Then X = S - {1,2} X {1,2} = S-C is irredundant and so are all supersets of X (refer to Figure 2.4.6). 2) Let S = {0,1,2}. Then X = S - {(0,1,0),(1,2,1),(0,2,0)} is irredundant and so are all its supersets. 2.5 Conclusions The results of sections 2.3 and 2.4 have important implications for automatic construction of irredundant sets. We will summarize the more important ones among them. Suppose that a Cartesian set S is given and we want to automatically generate irredundant subsets of S. Clearly any proper Cartesian subset C of S can be generated easily. Then so can the set difference S-C. Both of those were proved to be irredundant. If C is such that C t Sa, for all cXED, we proved that every superset of S-C is irredundant. All such supersets can again be very easily generated. Finally, we can easily generate minimal independent subsets of S (especially those of Example 2.3.2), which were also proved to be irredundant.

58., \ ~ X,= S C — xD c Cl ) IS c / s/ /'Y xHI z, YI X = S-C D YD 1 1 / / Figure 2.4.5: Illustration of the Proof of Lemma 2.4.1. 0 0 0 0 0 0 1 1 1 1 2 ~..... ~ 2 2 2 2 2 n 2 1 a2 02 G (S) G (C) G (S-C) 0o 0 0 0 0 0. ~ 11 1 11 2 Y2 2 2 2 - -2 C1 G (X1) c2 l G(X2) X 2 X1 2S-C X2DS-C X3 S-C Figure 2.4.6: All Supersets of ( X S - X C ) Are aeD a, D Irredundant, Where C _ S

59 Thus there is a subclass of all irredundant subsets of S, which can be easily automatically generated on the computer. The results of this chapter also often facilitate the verification of irredundance of sets under consideration. For example once we know that a set is a union of a family of nondisjoint Cartesian sets, we know it is irredundant without any need for further verification. Same goes for other types of sets, for example a projection of an irredundant set onto any subset of its index set. If a set is known to have s.e.p. property it is irredundant if and only if it is Cartesian. Verifying whether a set is Cartesian is clearly much easier than verifying its irredundance directly from the definition. Checking if S has s.e.p. is again facilitated by Proposition 2.2.6. We do not need to check whether every permutation of S has e.p., but just whether all cycle type of permutations of S have e.p. The problem, which still remains open, is that of finding a minimal irredundant superset of a given set X. It is hoped that the closure of a set X with respect to extension property will turn out to be useful in generating a minimal irredundant superset of X. The solution of this problem will have implications for the design of experimentation strategies. Why this is so will become clear in later chapters of the thesis.

CHAPTER III FUNCTIONS WITH STRUCTURED DOMAINS 3.1 Introduction In this chapter we will discuss properties of functions from structured domains, whose codomains are arbitrary abstract sets (not structured). The results obtained here will be later used, when functions from structured sets to structured sets will be considered. In particular the results are going to be applied to finite autonomous discrete time systems, where the functions involved will be the transition functions on a structured state space. We will start by introducing the concept of a location of a function. This concept refers to a minimal subset L of an index set, such that IL refines the partition of kernel equivalence of a function. We next explore the relations between locations of functional restrictions to a sequence of nested subsets of a function domain. Based on those results, we prove that for any finite family of functions with a common, infinitely countable domain, there exists a finite domain-subset X with the following property: for every function f in the family, L(f) = L(flX), where L(f) and L(fiX) are the families of locations of f and fIX respectively. We will then discuss extensions of functions from proper domain subsets with given locations. Finally, for finite Cartesian domains, we show how to construct

61 proper domain subsets with special properties. Namely, given an upper bound on a location size of the function, we construct a minimal proper domain subset such that the restriction of the function to the subset determines uniquely the function itself. 3.2 Properties of Function Restrictions to a Family of Nested Domain-Subsets The notion of a location of a function is intimately related to that of a location of a partition. Actually it will be defined to be a location of a partition of kernel equivalence of a function. We recall that for a function f from S, a kernel partition of f denoted by Hf, is a partition on S defined by: sHfs' iff f(s) = f(s'), for all s and s' in S. Definition 3.2.1 ([Zl]) Let f be an arbitrary function from S, where S C XSO. (ED D' C D is a location of f iff D' is a location of Hf. U Definition 3.2.2 ([Z1]) A function f from S, where S CXS, is in reduced form if D is zED a location of f. CA In the sequel we will denote the family of all locations of f by L(f). In case the location of f is unique we will often denote it by L(f). The restriction of f to a subset X of S will be denoted by fiX. We will now show that for any two subsets X1 and X of S, where X1 C X2, the following relation holds. For an arbitrary function f

from S, every location of fiX2 contains at least one location of fJX1. We also prove that the converse of this statement is not true. That is, there might exist a location of (flXl), which is not contained in any of the locations of (fiX2). Proposition 3.2.1 Let f be a function from S C >S and let X1,X2 be any subsets of S, where X1 C X2. Then a) for every LCL(fiX2) 3 an L~L(fIXl) s.t. L L but b) the statement "for every LEL(flXl) 3 an LEL(flX2) s.t. L C L is not generally true. Proof X X X X a) Let LEL(f!X2). Then 2RL <.11fx We note that HL1 = LX1) XI X2 X X X and f X = (llfl2X1). Hence (HL1 X1) < (l X1), i.e. L X But this implies that L contains a location of fJX1. b) It suffices to give a counterexample. Consider S = {(a,b),(al,(a(,b2),(a2,b),(ab2)} = {al,a2} X >{bl,b2}, where D = {x,$}. Let X1 = {(a1,b1),(a2,b2)} and let X= S. Clearly X1 C X2. Let f be an arbitrary function from S with a kernel partition 1 = ({ (a,b2),(a,b), (a2,bl),(a2,b2)}. X is irredundant and thus f has a unique location. L(fiX2) = L(f) = L(IT) = {cc. X X 11fII = {(a1,bl), (a2,b2)} and L(flX1) = (f X ) = {{O}'{B}}' Obviously 83 0, which completes the proof. C

Remarks 1) If JL(f lX) I = 1, that is if fiX1 has a unique location, then this location is contained in every location of f X2, where X1 C X2. 2) For any sequence of nested irredundant subsets of S, the corresponding sequence of locations of function restrictions to the subsets is totally ordered by set inclusion. We show next that for an irredundant set S and any irredundant nonempty subset X of S the following holds. If f 1 and f2 are arbitrary functions from S with equal locations, such that the kernel partition of f1jX refines the kernel partition of f21X, then the equality of the location of f2 and the location of f2 IX implies the equality of the location of fl and the location of f1jX. Proposition 3.2.2 Let S be irredundant and let f1,f2 be arbitrary functions from S s.t. L(f ) = L(f2). Then for an arbitrary honempty irredundant subset X of S, if (lf IX) < ( jf X) and if L(f2) = L(f2|X), then L(fl) = L(flX). 1 2 Proof Hf IX < Hf IX L(Hf IX) D L(Hf IX), i.e. L(f lX) D L(f2jX). 1 2 fl 2 1 — X2 But L(f2 IX) = L(f 2) = L(f ) and so L(f1 X) D L(f 1). By Proposition 3.2.1 L(fl) D L(fliX) and hence L(fl) = L(flIX). 0 Suppose that X1 ~ X2 2 X3 C S and that L(f X1) = L(f X2). One might then attempt a guess that from this point on the equality of families of locations of f restricted to supersets of X2 will obtain, in particular that L(fiX3) = L(fiX2). As we illustrate below, this turns out to be a misleading guess.

64 Example 3.2.1 Consider S = {0,1}3 and X1 = {(0,0,0),(1,0,0)}, X2 = X1 U {(0,1,0),(1,1,0)}, X3 = S. Let D = {o1l,a2,%3} and let f be any function from S with a kernel partition Hf = {(0,o,o0) (O )(l,, (1,O,0), (1,,0),(0,O,1), (0,,1), (1,1,1)}. We note that X1,X2,X3 are Cartesian and so irredundant. 5flX = {(0,0,0), (1,0,0)} and flX = {(0,0,0)0)( (10,0),(1,1,0)} L(fIX1) = {c1}, L(fIX2) = {ol} and L(f) = {ol,,Ot3}. So L(fJX1) = L(fIX2) $ L(flX3). This illustrates the above assertion. n The example is illustrated by Figure 3.2.1. We next show that if a set is a union of a pairwise nondisjoint family of Cartesian sets, then for any function from this set there exists a decomposition of its location along the "constructing components". Namely, the location of the function is equal to the union of the locations of its restrictions to all the sets of the family. Proposition 3.2.3 Let S = XSe and let Y be a family of Cartesian subsets of S s.t. oteD for any C,CSY, C nC c. Further let X = UC. CcT Then for any function f from X L(f) = UL(f C). C E' Proof Let LC = L(flC), for all CzE. Since C CX, by Proposition 3.2.1 L = L(f) D LC, for all CE1. So L _ ULC holds. We need to show that KC C D L, or equivalently that for any x,ycX if xlU I y then C&1_, tC

S = X /\0(~'~~) A 1 L(ITflX1) = {Cta1} ~ A_ L(1Tf X2) =(1, { (l 01 0) lu ~kL(TIf) = o =1} Figur 3 Ex l (1,.).~~~~~~~~~~~~(~)={~,z,~

66 f(x) f(y). Let x,y be such points. Then xcC,yeC, for some C,C in 'Y. Also XLc ULEY and since C 0n C # E, 3 a zECnC s.t. xI UL zI (See the proof of UL C C[L Corollary 2.4.1.) So xllL z and ylL LZ. Since x,z~C, y,zEC and LC and L- are the locations of fJC and fJC respectively, f(x) = f(z) and f(y) = f(z) hold. Thus f(x) = f(y), which was to be proved. a Remark The equality of Proposition 3.2.3 does not necessarily hold for a pairwise nondisjoint family V of irredundant sets, which are not Cartesian, even if their union is irredundant. The location of every function f from _X always contains UL(fIX), but this containment XE X~ may be proper. [5 Example 3.2.2 a) Consider X = {(0,0),(1,O),(1,1)} U {(1,1),(2,1),(2,2),(0,2)} XI U X2. All X1,X2 and X are irredundant and Xl1 X2 # p. Let f = {(0,0),(l,0),(1,1), (2,1),(2,2),(0,2)}. Then L(Hf) = {cl,c2}. lflX1 = {(0, 0),(1,0), (1,1)} = I and L(HlX1) = c. HfX2 = {(1,1), (2,1),(2,2),(0,2)} and L(H[jX2) = {cl}. L(Hf) L(f [Xl) U L(lfIX2), for {ot2 2 {ot}. (For illustration refer to Figure 3.2.2.) b) Consider X = {(0,0),(1,0)} U {(1,0),(1,1)} = C1 U C2. Cl n c2 = {(o,0)} # ~ and C1,C2 are both Cartesian. Let f be any function from X with a kernel partition Hf = {(0,0), (1,0),(1,1)}. Then L(f) = {acl} and L(fJCl) = {al }, L(f|C2) =. Clearly L(f) = L(fJCl) U L(fjC2). (For illustration refer to Figure 3.2.3.) O

67 0 0) 0 0 0 0 ] 1 1 1 1 1 2 2 2 2 2 2 a I G(X) i2 C1l G(X1) 2 al ((X2) t2 '(0 X 2,,1)4(2,2)j H 2 IT 'f H ' v:X2 XO., 0 X if, X I.(1,O' L(f) = L(flXl) U L(flX2) Figure 3.2.2: Illustration of Example 3.2.2 a). X = C UC2 ~ (1,0 2 L(f)= {a1}!t~~ ~ L(fIC2= 1......... 1 (0, ) L(f!C1) = I G(C1) G(C2) Figure 3.2.3: Illustration of Example 3.2.2 b).

68 Next we will consider an infinite set S structured over a finite index set D and an arbitrary function from S. We will show that for any sequence jXi4 of nested subsets of S, which constitute its cover, i=l and any function f from S, there exists a point N in the sequence, such that for every i > N L(fJXi) = L(f). As a corollary we will then prove that same holds for every finite family of functions from S. Before we do that however, we need to establish some auxiliary results. We will now prove that for S and a sequence Xi; as above the -=1 following is true. Given any f from S and any sequence {Li} of locations, such that LiEL(flXi) and {Li.} is totally ordered by set inclusion, the sequence {Li} becomes constant and equal to one of the locations of f. Lemma 3.2.1 Let S C XS, where IDI = n. Let f be an arbitrary function CG~ c from S and let {Xi4 be a sequence of subsets of S s.t. Xi+l D Xi i=l for all i and S. Then if Li is a sequence of subsets of D, s.t. Li C Li+ and LicL(flXi), 3 N s.t. for V i > N, Li = LN and LNEL(f). Proof Our proof will consist of two parts. First we will show that 3 N s.t. Li = LN for all i > N. Then we will prove that LNEL(f). a) Since all Li are finite (this follows from finiteness of D) 1

69 and totally ordered the sequence becomes constant after a finite number of elements. So N as above exists. b) We first show that LN as above contains a location of f. To do so it suffices to show that S < Hf, i.e. that for any x,yzS s.t. xlLNY, f(x) = f(y). Since UX = S and Xi D Xi, 1 N s.t. both x i i+l- i x,y and y are in XN. Let N = max(N,Nx y). Then x,yzXN and LNcL(fIXN-). x,y Clearly xN y,and thus (fjX')(x) = (flX$)(y), which implies that f(x) = f(y). Hence LN contains a location of f, say L,LN _D L. We will show that LN = L. By Proposition 3.2.1, L contains a location of fIlXj, say L,L D L. Hence LN D L, where LN,L are both locations of f| X. This implies that LN = L and so LN D L D L implies L = LN. Thus for all i > N, Li = LN and LNEL(f), which was to be proved. O From now on, unless mentioned otherwise, we assume that S C > S acD where cardinality of D is finite and equal n. In the next lemma we prove the following result. We assume that a sequence {Xi} of nested subsets of S is given and that f is a function from S. For every set Xi in the sequence we choose a nonempty subset of L(flXi), L.. This way we obtain a sequence. Provided that i were chosen so that for every i and every location in Li+l there is some location in Li contained in it, there exists an infinite sequence of locations Li =l, where L ~Li and L +l L. The existence of such a sequence is not obvious at all and to prove it we employ a graph theoretic result known as The Infinity

70 Lemma. (For the statement and proof of generalized Infinity Lemma the reader is referred to [BW1].) Lemma 3.2.2 Let {Xi be a sequence of subsets of S s.t. Xi+ D Xi, for all i, and let f be a function from S, where Li = L(flXi)' For every i, let Li be a nonempty subset of Li. If {i}~ has the property that for every i, every Leli+l. 3 an LELi s.t. L D L, then 3 an infinite sequence {LiJ s.t. LiLi and L D L.. ~~LiSl i=l Li+1 - Li. Proof Since D is finite so is clearly each Li. Let Qi be a subset of 1 1 Li X Li+l i = 1,2,..., s.t. for any LlELi, any L2 Li+l' (L1,L2)EQi -4 L1 C L2. Then each Qi is finite and nonempty, since every LELi+1 contains at least one LEL.. i3-l 1 Also the first point of every pair in Qi+1(i=l,2,...) is the same as the second point of some pair in Q.. All conditions of the Infinity Lemma are satisfied and thus 3 an infinite sequence {L4 s.t. (Li'Li+1) Qi' V i. We note that this sequence is totally ordered by set inclusion, since by our definition of Qi', (Li,Li+l)CQi > L C L+l' Also LiEL.. This is a desired sequence. 1 1 The proof is illustrated by Figure 3.2.4. Theorem 3.2.1 Let Xi be a sequence of subsets of S s.t. Xi D X and ~~xd a ~~~i+l-i

71 X ~1,1 1,2 71, Llk 2,1 2,2 L2,k2 X2 -/L3 1.3,2 L3,33 _,k3 x3 Figure 3.2.4: Graphical Illustration of Lemma 3.2.2.

72 Jxi = S. Then for any function f from S, M N s.t. for all i > N, L(flXi) = L(f). Proof 1) First we show that 3 N s.t. for all i 2 N, L(f) C L(f1Xi). We will denote L(f]Xi) by Li. Let I L(f) = >- 1. We will proceed by finite induction on the number of locations of f contained in L.. a) Induction base. We show that at least one of the locations of f is contained in Li, for Vi ~ N, some N. By Proposition 3.2.1 for every LeLi+l 3 an LELi s.t. L D L. With L = L Lemma 3.2.2 can be applied. Thus 3 a sequence iil s.t. LiEL and Li C Li By Lemma 3.2.1 then 3 N s.t. L. = LN for Vi > N and LNEL(f). Thus 3 N s.t. at least one of the locations of f(LN) is contained in Li, for v i > N. b) Induction step. We show that if 3 N s.t. k locations of f are locations of (fIXi) for V i > N, where k < Z, then 3 an N > N s.t. (k+l) locations of f are locations of (f Xi) for all i > N. Let {L i,Li,...,Lk} be locations of f s.t. L ~L, for 1 2 k i j = 1,...,k, i > N. Then Li are locations of (flXi) for all i > N and thus it suffices to show that 3 N > N and 3 L L(f) - {Li,Li,...,Li ik+l k s.t. L. ~L. for all i > N. k+1 1 kl > Let L. = {L,...,Lik} for all i > N. We note that Li. 6 V i > N. For suppose Li = C for some i >2 N. Since IL(f) > k, C(f) = L(f) - {L. 'LIL } #. So let LL(f). Then by

73 Proposition 3.2.1 3 Lc~L- s.t. L DL, but then L = L- for some i - 1 jE(l,...,k). This implies L D L-. Since L- eL(f), this in turn 1. 1 -I J implies L = L-, in contradiction to our assumption that LCL(f). We now want to prove that for all i > N, if LLi+ then 3 an i+l' LEL. s.t. L D L. We know that this holds for ti+l and Li, i.e. that for every LEL i+l an LELi s.t. L D L. We need to show that LELi or equivalently that L # L. for j = 1,...,k. Suppose L = L. for some Lj 1j j. L. is a location of fXi+ and so L D L. -- L = L. This ~~iJ ~i+l j contradicts LE +. Thus LEL.. i+l' 1 Now all the conditions of Lemma 3.2.2 are satisfied and thus A a sequence i N s.t. L s iEi and. By Lemma 3.2.1 then A N > N i=N s.t. Li = Li = L for i > N and LeL(f). Since L.cLi. V i, Le(f) holds. 1 i+l 1 1 We showed then that 3 N s.t. L(f) C L(fIXi), V i > N. 2) We still have to show that 3 an N s.t. for all i > N, Li = L(flXi) = L(f). Let N be s.t. L(f) C L(flXi), V i 2 N Le = Li - L(f), V i > N. If 3 an N > N s.t. ri = ~ for all i > N, then obviously Li = L(f) for i > N and we are done. Suppose that such an N does not exist. Then A a sequence of natural numbers N 0 s. t. NiNi+1 - N i. and L As before we show that IN. satisfy the conditions of Lemma 3.2.2 and so A a 1 sequence of locations Lii= s.t. L C L.L LC By Lemma 3. 2. 1 then N s.t. L = L, for all i > N and LEL(f). But LL = L -(f), 1 1 Ni N. V i, which leads to a contradiction. So N as above exists. Q

74 Corollary 3.2.1 Let iXi} be a sequence of subsets of S s.t. Xi+l D Xi and S. Then for any finite family F of functions from S Xi r S. Then for any finite family F of functions from S M an N s.t. for V i > N and any fEF, L(fIXi) = L(f). Proof By Theorem 3.2.1 for every fzF X NJf s.t. for all i > Nf, L(fIXi) L(f). Simply take N = max Nf. * fEF As a corollary to Theorem 3.2.1 we will show that for any finite family F of functions from an infinitely countable set S, there exists a finite subset X of S with the property that for every f in F, L(f) = L(fjX). This is to say that to find a set of locations of any function in the family we just need to know the function on a subset X as above. It is important to mention that although the existence of such a set is guaranteed, this set is not known a priori. For any nested sequence of finite sets, which cover S, from some point on every set in the sequence has the desired property. Suppose that S is irredundant and without loss of generality that we consider a single function from S, cardinality of whose location is a priori known. Then "experimenting" we obtain the function values on a sequence of nested subsets and after a finite number of steps we find the location of the function. It is the knowledge of location cardinality which tells us when to stop. We stop when the cardinalities of the location of the restric

75 tion and of the location of the function are equal. Without this knowledge however, we never know whether we have already reached the location or whether we still need to go further, unless of course one of the locations is equal to the index set D. Corollary 3.2.2 Let ISI = 0L Then for any finite family F of functions from S H a finite subset X of S s.t. L(f) = L(flX) for all f~F. Proof Let {si=l be an enumeration of S. Let X1 = {sl} and Xi+1 = Xi. J{si+l}, for V i > l. Then X D, X= S and V Xi's are finite. Thus be Corollary 3.2.1 a N s.t. for V i > N, L(fIXi) = L(f) for all fEF. Take X = XN. [ Remark We note that for arbitrary S there is no proper subset X of S such that for every function f from S to some codomain R (with IRI ~ 2), L(f) = L(fIX). (Given X let f be a function with the kernel partition If = {,S-X}. Then L(fIX) = {4} and since Nf # I, L(f) # L(fIX)). [ Corollary 3.2.3 Let S be a countably infinite set, s.t. S = XS- X C, where c~D OCED C C S, for all acD. Then for every finite family of functions from S 3 a finite irredundant subset X of S of the same form as S s.t. for every feF, L(f) = L(fiX).

76 Proof Let si. be an enumeration of S. With DI = n we construct a sequence __ of subsets of XS a, where X = n{(s,s S ) i i=l acD ct1 2 ) 0- (so 0 o o 0 X1 =X U {(s S2,s,,.,s )}, X2 = X1 U,so,...,s ), C t! 2,3 e 2 n1 a2 O,3 n1 n n (,s, s1,...,so )}, etc. That is at the i'th stage we add to Xi, o a, n i1 2 C3 all points in X S a, which are in ct~D P (x ) X P(X.) X...x P (x.) )X S x (x P (X... X (x. l kif i i[n + 1 if[iJ < - (imod n mif od n n n~l n where ji i and k 4 er ii }. if [1] = 1 j n if imod n = n Lnn n For any number r [r] denotes the largest integer not greater than r. Clearly all Xi's are Cartesian by construction and = X S X - X. hold for all i. i+l 1 For every i, let Y= X. -XC = X.i - Xi n c, where X.'s are csD as constructed above and C =XC. X. i C are Cartesian, since both aFED X. and C are. Thus Y. is a set of the form of S (and of Proposi1 1 tion 2.4.5) and thus irredundant. Clearly Yi+l D Yi for all i and Yi = JXi.- C = S-C. So by Corollary 3.2.1 3 N s.t. for V i > N, V fCF L(f) = L(fjYi). Take X = YN. Example 3.2.3 Consider S = S1 X S2 where S. {S 0. Then the first i =i few sets in the sequence {Xi} of Cartesian subsets of S, such that Xi+ Xi and U Xi S are given below. ~~~i-~

77 x s o ox) XO - - f~ 1,S2 S 3 X1 = X 0 ~J S1 S2,S} (,S2 S3), X2 = X 1 1,SOS (s 1,S,S3) s1 2 1 -(S1 S2mS13 x X U (S 2 S1 0S 1) i ( S 2 3) (S 2 S 2 S ~) s1's2 3)' 1 2 3 (S 1,S2,S ~), X X U (s 1 S 2 S 1 1' 0 ) ( S 2 S 3 Througholut this section we deal with functions from a structured domain S to a codomain R. It is assumed that the cardinality of R is at least two, thus allowing nonconstant functions. R is treated as an abstract nonstructured set.

78 When a function f is known on a proper subset X of S only, several questions arise. For example, for every location L of f we want to be able to count all extensions f of f to S,with the property that LEL(f). Also for every LcL(f) and an arbitrary subset L of the index set D containing L, we want to count all the extensions f of f to S with the property, that there exists a location of f equal to L. The importance of answering those questions will be clear in later chapters, where the above results are going to be used to compute confidence in a given partial model, average confidence, predictive confidence and other parameters of interest. We first establish some notation. With f a function from a proper subset X of S to R and F the family of all functions from S to R (X) E(SIO) denotes the set of all extensions of f to S, in F. Ef(X) (L denotes the set of all extensions f of f s.t. (S,R) fEF and LEL(f). f(X) ( L denotes the set of all extensions f of f, s.t. (S,R) - ' fF and 3 an LEL(f) s.t. L C L. f(X) f(X) denotes the set of all f s.t. fcE and 3 an E m(,ub) ' (S,R)a (S9R) LEL~(f s.t. IL! < ub. f(X f(X) We will often write E (SR)(L) instead of E(SR) (L, ) and (SR) (S,R) f(X) f(S) (C L) in place of E (C, L,) (s,R) (SR) Also when the sets S and R remain constant, we will drop (S,R) subscripts, for example Ef(X) will be shortened to Ef(X) Same holds (s, r willpbe (S,R)

79 for superscripts, e.g., when X is constant we will often write E(SR) (S R) instead of Ef(X) (SR). For an arbitrary subset X of S and an arbitrary subset L of 1) we introduce a set called completion of X w.r.t. L and S, denoted by COMPLL (X). Definition 3.3.1 For an arbitrary X C S C XS and an arbitrary L C D, COMPLL(X) = {s scS and 3 xcX s.t. sHLx. X} L We remark that for any L C D, COMPL (X) D X. Also COMPLs(X) = S, while CONPLD(X) = X. It is possible that although L i D, COMPL (X) = X. S S We will now show that for any chain of subsets of D the corresponding completions of X also form a chain, but reversely ordered. Proposition 3.3.1 Let X be a subset of S and let {L1,...,Lk} be subsets of D, where Li C Li+,i=,...,k-l. Then {COMPLSL(X), COMPLs2(X),...,COMPLSk(X)} L. L form a chain, where COMPL i(X) D COMPLS (X), for all i = 1,...,k-l. S S Proof The proof is trivial and follows directly from Definition 3.3.1. Fix an iE(l,...,k-l). Then s~COMPLsi+l(X) iff 3 an x~X s.t. siL x. i+l But Li -D > sTL x, => ssCOPLS i(X). C Our next result is the following. Given a function f from a subset X of S to R, such that LEL(f), we show that for any L L, if there

80 exists an extension f of f to S, such that fE Ef() (L), then the (S,R)L restriction ~ of f to COMPLs(X) is unique and L is a location of f. Further we give the definition of f on CONPL (X). Lemma 3.3.1 Let X C S and let f be a function from X to R with LZL(f). Then for any L s.t. L C L C D and any fEef(X) E(L) (provided E (L) (S,R) (S,R) a) f = f COMPLL(X) is unique b) f is defined by L f(s) = f(x), for all sECOMPL s(X), where x~X is such that sllLx. c) LEL(f) hold. Proof Let fE f(X) (L) be given. (SR) 1) We first show the uniqueness of the restriction f of f to COMPLL (X) = Y. f E(X() (L) — > < f. Let sECOMPL(X). Then by Definition 3.3.1 3 an xcX s.t. sH'Lx. This implies that f(s) = f(x). Thus f(s) = f(x). We need to show f is well defined. Let y # x be a point in COMPLS(X) s.t. sHLY. Then xlLy holds and so x1Ly, since L D L. But LZL(f) implies then that f(x) = f(y). Hence a) and b) are proved. 2) We now prove part c). To show that L~L(f) it suffices to show that - < Hll. For this inequality implies that L contains some location of f, say L. But then by Proposition 3.2.1 3 an L'eL(f) s.t. L D L'. So L D L D L' holds. Since LSL(f) and L'CL(f) however, L = L' and thus L = L, which means

81 that if < ll^, then LcL(f). So let s,s'EY = COMPL (X) be such that sL-s'.. 3 x,x'~X s.t. siL x and s'l x' By part 1) of the proof f(s) = f(x) and f(s') = f(x'). Since L D L, sT[Lx and s'llLx' hold. Also sIIs' => xll;x'. But L~L(f) - f(x) = f(x'). Thus f(s) = f(s') and < II, which was to be proved. 0 Corollary 3.3.1 Let X C S and let f:X -* R, where L is a location of f, i.e. L~L(f). Then for any L, s.t. L C L C D f (COPLLS(X) f(x) S E(S R) (CL) = E(SR) (CL), where f is the unique extension of f to COMPL (X) of part b) of Lemma 3.3.1. Proof Since f is an extension of f, clearly E(Y)( L) C Ef(X)(C L), where Y = COMPL '(X). We need to show that E (CL) C E (CL). Let feE (CL). Then 3 L,L C L C L s.t. LEL(f) and LeL(f). But by Lemma 3.3.1 then L L f COMPL(X) = f, where f(s) = f(x), for scCOMPLs(X), where xcX is such that sfVNx. Since L C L, COMPL (X) C COMPLL(X) holds. We show that f COMPL (X) = f, where f is as above. L ^ For any seCOMPL (X), f(s) = f(y), where yX is such that sCy. But sLY l = silty =2 f(s) = f(y)= f(s) for V sCOPLSX). Clearly f COMPLL(X) = fjCOIPLL(X) = f and so fE ( (CL), which was to be proved. Given a function f from a subset X of S s.t. LeL(f) and any

82 L D L, we show how to construct all extensions f of f to S, such that at least one of the locations of f is contained in L. Theorem 3.3.1 Let X C S and let f:X - R, where L is one of the locations of f. Then for any L, s.t. L CL CD, cf(X) f(X) LX E( (C L) If f lCOM P L(X ) f and I f > }, L where f is the unique extension of f to COMPL (X) of Lemma 3.3.1 and II is a partition on S defined by (ji1H^ [for sECOMPL (X) [sin= [s] for s S-COMPL (X) Proof We note that by Corollary 3.3.1 we need to "count" only f (COMPLL (X)) L E (C L). Thus clearly f6E(SEX) (L) =2 f COMPL5(X) = f. We show next that H as above is well defined. It suffices to show that S-COMPLL(X) L = z] S. Equivalently we just need S zS-CONPLL(X) HL L L to show that for every zES-COPLS(X), [Z]1S C S-COMPL (X) or that for any sES s.t. ZHLs, xEX s.t. sHLx. This is obvious for given an sES s.t. slHLz, if S an XEX s.t. xHS s, then xILS,# to zES-COMPL (X). So H is well defined. Also since LEL(t), it is easy to show that S<. HL L A a) We show that if f is such that f COMPLL(X) = f and f > 11, then fee~ (Y) (f- L), where Y = C0~fPLL then feE ) (CL), where Y = COsPL (X). Clearly f is an extension of f so we have to show that 3 L C L s.t. LEL(f). To do so we just need

83 to show that SlL < f. But 11 < H < H L <_ b) We now show that if fE f(C (L) then fj = f and f > 11. That flY = f is obvious. Now a1 an L C L s.t. LEL s.t. (f). This implies that H_< lf, implies that HS < f Let x,yES be such that xlly. Then by definition of ii either x,yCY or x,yES-Y. If x,yEY, then xlTy -= f(x) = f(y) -> f(x) = f(y). If S S x,yES-Y, xHy; XIILY m xHIfy, since we showed that HL< f. This completes the proof. Theorem 3.3.1 will be later illustrated by an example. Given f as in Theorem 3.3.1 and an arbitrary L D L we will now show how to find the set of all extensions f of f, such that L~L(f). Proposition 3.3.2 Let X be a subset of S and let f:X + R, where LSL(f). Then for an arbitrary L s.t. L C L C D, Ef() (L) f(X) (CL) - U E( () (SR) (S,R) (SR) L;L Proof This is obvious, since from the definition of E (CL) it (S,R) follows that Ef(C L) = U Ef(L) = Ef L)U Ef(L). Also for any LCL LCL L L, E (L) n Ef (L) =. Proposition 3.3.3 Let X C S and let f:X -+ R, where LeL(f). Then a) E(X) (CL) = Ef(x) L) and

84 f(X) f(Y) L b) E (S (L) ) =E (L), where Y = COMPL (X) and f is the exten(S,R) ' sion of f to COMPL (X) defined by Lemma 3.3.1. Proof a) Let fzE (C L). Then 3 an L C L s.t. EL(f). Also 3 an LEL(f) s.t. L D L. This implies that L D L. But since both L and L are locations of f, L = L and so L = L. So fsEf (L) and E (C L) C Ef(L). Clearly E f(L) C E (C L) and thus a) has been proved. b) Part b) follows directly from Lemma 3.3.1. 0 We will now illustrate by an example how to construct extensions with desired locations. Example 3.3.1 Consider S = {0,1}3 and X = {(0,0,0),(1,0,0),(1,1,0),(1,1,1)}. Then S and X are irredundant (X by Proposition 2.3.2) and S is actually Cartesian. Let f be a function from X to R = {0,1} defined in Figure 3.3.1. Then f has the unique location {ld}. We are seeking all extensions of f to S with locations contained in {al,a2}. Since L(f) = {Tl} we are thus seeking all extensions of f to S with locations {dl} and {cl,2 }. {' a To construct those we first find the COMPL 1I 2 (X) and then use Corollary 3.3.1. COMPL{'2} (X) = x U {(O,O,1), (1,0,1)}. f as of Lemma 3.3.1 is defined by fX = f and f((0,0,1)) =f((0,0,0))=1, while f((1,01)) = f((l,00)) = 0.

'I '' aodtulxH jo suoTIoun. jo saTlqL:I' s oan lTd ~{ T} = ( J ) 1 {z,{ } = ( j) j = (X) 1dWOD|J = (X) SldWNOD I IJ { Z' Io} {rIr1} t 1''0. 0. O I ('1'0o) (0)' 1 O"' (o''0) o (TI'O') 0 (I'o'i) (i'o'o) (' o 'o) 0 (T V T) s s 0 (T' T t) 0 (1'T't) o (o'1'1) - (0... ( I ii) 0 (o'o'() T) (o' o') I ('o'o) [ c (o'o'o) (x) J x (x) x _ = x[j '{t}: (=){ 0 (1'o't) ~~(it~~~~~'o'o) ~( = _ 0'' 0) I ) (X) 1 diOD 0 0 (o'i't) o 't) Tx (;Id0'1 O(. I I) O C t o' I')) O'f ( ' i) (0'o'0) ' io'0o'o) (x)4 x (x)4 x

e2 } We note that S-COMPLS (X) = {(0,l,0),((0,l,) }, that is, there is one {ll block in (S-COMPL {a1a}(X)). {~C1,cz2} S We will now use Theorem 3.3.1. H of this theorem is defined by i= {(o -o,)(oo,1), (1,o,o),(1,l,o),(1,1,l),(1,0,1), (0,l,0), (O,l,1) All the extensions f of f, whose locations are contained in {al,2 } are those, for which fICOMPL (X) = f and n < ~f. There are two such extensions. One of them, fl, assigns value 0 to (0,1,0) and (0,1,1), and f2 assigns value 1 to (0,1,0) and (0,1,1). f1 and f2 are as in Figure 3.3.1. We easily check that L(fl) = {al,a2} and L(f2) = {al}. C We will show in the next corollary that for an arbitrary subset X of S, if f is a function from X to R such that LCL(f), there always exists an extension f of f to S, such that LcL(f). Corollary 3.3.2 Let X C S and let f:X + R. Then for any LcL(f) 3 an f such that f(x)) (L). If I P(S) and IRI are finite, then f (S,R) (L) Proof By Proposition 3.3.3, Ef(X)(L) = Ef(Y)(LEf(Y ) f(Y)(C L), where Y = COMPL (X) and f is as in Proposition 3.3.3. But then by Theorem 3.3.1 (*) Ef(X)(L) = {fffE f(Y) and L_< Nf}. But since IRI i O, clearly f as above exists. For example assign any value of R to all points of S-COMPL (X). (If the latter is empty S = COMPL (X) and there is a unique extension of f to S s.t. LcL(f)).

87 b) From equation (*) above it clearly follows that we get all the desired extensions by assigning all possible sets of values of R to lL blocks of (S-COMPL( X)). There are (IPL(S) - IPL(X) 1| L blocks of S in (S-COMPL ()). L blocks of S in (S-COMPL S IPL(s) I-IPL(X) I So there are IRI extensions f of f s.t. LEL(f), which was to be proved. As a corollary to Corollary 3.3.2 we will now show that if f is a function from X to R and LEL(f), there exists a unique extension of f to any subset of COMPLL(X) such that L is a location of this extension. Corollary 3.3.3 Let X C S and let f:X -+ R. Then for any LFL(f) and any subset Z L of COMPLS(X) s.t. Z D X, 3 a unique extension f of f to Z s.t. LEL(f). If L = L(f), then L = L(f) holds. Proof 1) We first show that 3 an extension f of f to Z s.t. LEL(f). By Corollary 3.3.2 3 an f, an extension of f to S s.t. LcL(f). Let f = f Z. Then L D L, where L~(f) and L 2 L, where LEL(f). Thus L I L and so L = L. This implies L = Y. Thus LeL(f) and the desired extension exists. 2) We next show the uniqueness of the extension. Suppose the extension is not unique. Let fl and f2 be two distinct extensions of f to Z, s.t. LeL(fl) and LEL(f2). Then by Corollary 3.3.2 applied to Z and S, 3 fl and f2 s.t. flEfl(Z) (L) and f2eEf2(Z)(L). Since X C Z C COMPLS(X), and fl = (fllZ) f2 = (f21Z) holds, clearly fljCOMPLs(X) # f2I1COMPLL(X). This however contradicts part a) of

88 Lemma 3.3.1. Thus the uniqueness of the above extension follows. If L is the unique location of f, then for every LcL(f), L D L. But LEL(f) =~ L = L(f). [1 Remark 1) For f:X -+ R and LEL(f), if L; L is such that COMPL (X) = S, then E (L) = ~. This follows directly from Lemma 3.3.1. 2) It can be shown that with f and L as above, even if S f COMPLs(X) and both X and S are irredundant, given L 2 L, the set E (L) may be empty. 3) If S is Cartesian however and all the conditions of 2) are met, E (L) # p. D It is easy to show that given an irredundant subset X of a Cartesian S and any subset L of D, the COMPLL(X) is irredundant. This need not be the case when S is irredundant but not Cartesian. In either case though, if f:X -+ R and L = L(f), every extension f of f to COMPL (X) such that LEL(f) has the unique location L. (This was proved in Corollary 3.3.3.) 3.4 Construction of Domain-Subsets with Special Properties Throughout this section we will assume that S is Cartesian and that cardinality of every S is at least two. We will start by constructing,for every subset L of the index set D, an irredundant subset X of S with the following property: for every function f from S, whose location is contained in L, L(f) = L(fIX). Actually we will construct a parametrized family of such subsets. All sets of the family will be alike —have same cardinality and

89 essential structure. They will be shown to be minimal in cardinality among all the subsets with the described property. Using as constructing elements the sets described above, for every integer k, (O < k < IDI), we will construct a parametrized family of irredundant subsets of S, each of which has the following property: for every function f from S, such that IL(f) < k, the locations of f and its restriction to the subset are the same. In the sequel we will use the following notation. For any subset X of S F(X,R) denotes the set of all functions from X to R denotes the set of all functions f in F(X,R), such (,R)' that LcL(f) denotes the set of all fzF such that 3 an (x,R _ (xR) LeL(f) such that L C L. F (*,ub) denotes the set of all fcF R) such that [A an ((X,R) ) (XR) (''b LFL(f) with iLJ < ub. F(XR) (Lub) denotes the set F (,R)(L,') f F(XR) (,ub). We will often shorten our notation in an analogous way to the one described in section 3. Definition 3.4.1 Let S = XS. and let L be an arbitrary subset of D. Then for olcD any yES, X is defined by 4 = {sIsES and PDL (S) = DL(Y)} It follows directly from the definition of XL that for any two points y and y of S, such that PDL(y) = PD-L( y)' and are equal.

90 As a matter of fact XL and XL are equal if and only if PDL(Y) = D L(y We also note that P(S) = Pj( ) for arbitrary L C L and any y in S. This obviously implies that for every L C L, the COMPLS(X) is equal to S. We can think about XL as defined above as a subset of S, for which all a coordinates of L are open, that is vary over entire S, and all coordinates of (D-L) are fixed and equal to those of y. We will sometimes denote XY schematically using U to denote an open coordinate. Thus for example if D = {1,2,3,4}, then 300 Y3Y4 denotes 2}where y = (Yl,Y2,Y3,Y4) We note that Xy = {y} and Xy = S. We will summarize the important properties of XL sets in the theorem to follow. First we will establish an auxiliary result to be used in its proof. Lemma 3.4.1 Let S = XSU, where IS j > 2 for all ocD, and let L be an arbiOtED trary subset of D. If ZL # c is an arbitrary subset of S with the property that for every fEF(SR)(L), L(f) = L(flZL), then ZL contains at least one point from every equivalence class of SII. Proof If L = ~, then any ZL s.t. I Z > 1 works. (Since then ItS has 1 equivalence class.) So assume L # ~. Suppose 3 an equivalence class Lof S [XI] S.t. ZL = [X] = Let a,bER, where a $ b and let f be a function defined by f([x] S) = a and f(S-[x] S) = b. LL L

91 - - 0 cS Then If = {[x] S' S-[x]I S L(f) = L, since L < and for every L L aEL, IS Nf. (This follows, since for every cCL A~ xCS-[x] S s.t. S X L_ x but x L x.) We note that ZL r S - [x] S and so L(flZL) = L # L. Thus 3 f, feF(SR)(L) s.t. L(f) $ L(fIZL) and this contradicts our assumption. So indeed ZL contains at least one point from every equivalence class L* of QL' Corollary 3.4.1 Let S = S, where IS! > 2, V aED. Then the only subset ZD of ocD S with the property, that for every fEF(S,R)(D), L(f) = L(fIZD) is S itself. Proof We simply notice that [x] o = {x}, V x~S. We then apply the above ED lemma. [E We will now illustrate the construction of XY sets by an example. Example 3.4.1 Consider S = {0,1}3, where D = {ata2, a}. Then X(0,0,0))} X(0,0'0) {(0,0,0 ), (1,00)} (0,0,0) = {(0,0,0), (0,,0) ((,o,0), (1,1,0)} x{o1 c2 } {cOx9Hesa7}

92 We note that X01 X (0 'a 0) Also X (1,c 1) = {(0,1 1) (11,1)} and X} =')1 We will show later that I1X = XYI, for any y,yES. For the illustration refer to Figure 3.4.1. [7 Theorem 3.4.1 Let S = XSL where IsaI ~ 2. Then the following hold. cED a) for every y~S, every L CD, 4 is irredundant. b) I4!= I m where m IS I, for V L ( and I XYI = 1 aCL c) for any y,yES and any L C D, 4X1I = IXI d) for any yES, any L1 C L2 C D, 4 C, and if L: $ L2, then 4L 2. e) for any yeS, any L C D, if fsF(S, R)(C L), then L(f) = L(flX) f) for any yeS, any L C D and arbitrary L C L, if fEF (L) (4,R) then 3 a unique extension f of f to S, s.t. L=L(f). g) for any L C D, if ZL is any subset of S s.t. for V fEF(SR) (CL), L(f) = L(f1ZL), then IZLI > 141 for every y~S. Proof a) X is actually Cartesian, for XY IS Ot if oEL where X = {y} if ocD-L b) This follows from part a) of the proof. Since for L =, = {y}, IXY = 1. For L,, since XX, where X 's cwD

93 (o,oi,o) X~~~~~ x {U3 (01 0.,o 1 X{cll,c~2} (1,9I 1 l} a1 I ~~~(1. 0) ) I (10,1I.9 (0,1,0) (11,1,X Figure 3.4.1: Xy Subsets of So Lc1

94 are as above, I4! = ]'Ixi = I[xL = iIsJI. c) This follows directly from part b), since IXY] is independent of y and depends only on L. d) Let sY4. Then S But since Ll C L2, D-L1 D D-L2. d) Let sThen s D-Ly Hence s %L2Y holds and thus sEX by Definition 3.4.1. For L1 J L2, let s be the point of S defined by (y for acD-L2 =, where y = (y) and z = (z). z for aE L2 z is any point ofS s.t. z: y for all aED. Then clearly s4, but, since _ (s) PD-L (y) (z # Y on (L2-L )). e) Let L,y be arbitrary but given and let fEF(S, R C L). Then 3 L C L s.t. L(f) = L. We denote f = fXy. LetL = L(f). Then clearly f(XY) L D L. Also feE (L). As we noted before COMPL (X) = S. We use Lemma 3.3.1, all of whose conditions are met. By this lemma LCL(f). But S is irredundant, which implies L = L. Thus L(f) = L(fI X), which was to be shown. A L f) Again we note that for every L C L, COMPLS(X ) = S and we apply Corollary 3.3.3. (Remember that both XY and S are irredundant.) g) We notice that 4 has exactly one point from every equivalence class of IE. By Lemma 3.4.1 any ZL as of part g) has to contain at least one point from every equivalence class of L. So clearly L' IZLI >~ 4!. L Although we do not intend to do it here, it can be shown that every set ZL satisfying g) of Theorem 3.4.1, whose cardinality is minimal, is an L set, for some yeS.

95 Using X sets as defined above we will construct Y sets, where k is an integer ranging from 0 through n. Given an index set D with cardinality n, we will denote by Lk the set of all subsets of D with cardinality k. Of course ILk = (k) = nk. Definition 3.4.2 Let S = S, where I DI = n, and let k be an arbitrary integer s.t. 0 < k < n. Then for any yes Y I= Iva It follows from the above definition that Yk is the set of all points in S, which differ from y on at most k coordinates. In other words for every seYy there is at least (n-k) coordinates a of D such that sa = ye. If d is a Hamming distance on S (i.e. d(x,y) = I{aP a(x) # P (Y)}) then Yk = {slseS and d(s,y) < k}. Unlike for X sets, Yk = Y if and only if y = y, except when L k k k =n. We also note that for any L, such that |Lj < k, P-(S) = P~(Yy) and thus COMPLL(Y%) = S. This follows directly from the fact that for any such L there is a subset L of D such that L C L and ILI = k. But then k C Yk holds, and as was noted before COMPLL() = S. As is easy to see YY {y} and YY -= = S. Also for every 0 n k < n, Yk is a proper subset of S. We are now ready to summarize the most important properties of Yk sets.

96 Theorem 3.4.2 Let S = X S, where IS. > 2. Then the following hold. aOD a) for every k, 0 < k < n, every yeS Yy is irredundant. b) IYYI = 1 for all yeS, and for m =IS 1Y + j 7(m -1), V k ~ 1 ikl LELi cEL In case ma = m for V cED Y i=O(n)(m-1)i c) for any y,ycS and any 1 < k < n, I YY = I Y d) for any yeS and any kl _ k2, Y C Y Further if k1- k2 k! $ k2 then YkY Y k k1 - k2' e) for any L C D s.t. I|l < k, L(f) = L(fjYY) holds for every fcF(SR)(L) (for V y, V k). f) for any k, any y if f:YY + R and IL(f) < k, then 3 a k unique extension f of f to S such that L(f) = L(f). Proof a) Y = are Cartesian and clearly {y}EQX. LELk LiLk Thus by Corollary 2.4.1 Yy is irredundant. k b) Yk = ZiY_ where ZY = {sjseS and d(s,y) = i}. Assume k > 1. k i k k All Zy sets are disjoint and so I YI = L[zYI = 1 + iziYi. 1i=0 i=l We can choose subsets of D with cardinality i in i ways. Li is the class of all such subsets. Clearly ZY = L Wy where WL is the subset of ZY, whose points are different from y on all coordinates of L and on 1

97 those only. IW = (m-l). Again for L L W = W and so L ll L L k I = L L(m -l). Thus IYY = 1 + L m 1)-l ~xCL i=l. i i For m = ma, V a, this becomes IY~I = 1 + (m-1)i = (m-l) 0 + ( m-l) = i~l i~l i=l c) follows directly from part b) d) Y = {sd(s,y) < k }, Y {sld(s,y) < k2}. So clearly if k < k2 Y holds. For - k2 k2 For k, ~ k2, Yk C Yk, since the set of points with distance k from y is nonempty. e) Let L be given, I| < k. Then 'I L s.t. L C L C D, IL| = k and X C YY Let fF (L) be given. Let = L(f Y). By part e) of XL- k' (S,R)k Theorem 3.4.1, L(fIXI) = L(f). But then since S DYD 4, L(f) D_ L D L(f) holds, which implies L = L(f). This completes the proof. f) Suppose there are two extensions of f, f1 and f2 s.t. f 1 f2 and L(f) = L(fl) = L(f2) = L, where ILI < k (f':Y + R). Clearly k CYk and by part e) of Theorem 3.4.1, L(fllX ) = L(fl) = L(f2|X-) = L. Since both fl and f2 are extensions of f, fllXl = f2IX- = f. But then L(?) = L and f l, f2 are two different extensions of f to S with location L. This however contradicts part f) of Theorem 3.4.1.C Corollary 3.4.2 Let S = XS, where ISJI = m, V a. Then the following hold. cxED a) for any L C D with IL| = g < k C =IP(S) - IPL(YY) I -

98 b) for any l > k and any L (_ D with ILI = l t L | at L(Yk~l = t (i)(m-l)k c= IPL(S)I I-~LY)L(YJ = Proof a) This is clear from the definition of Y. b) the proof of this part is analogous to the proof of part b) of Theorem 3.4.2, except that projections are taken. o As we shall see later c~-values will be required for confidence computations. It is then important that they be easily computable. Remark Every superset of YY is irredundant. We simply note that n-l S - YYn1 = {z d(z,y)=n} = (S -{y }) and use Corollary 2.4.2 a Suppose that given an integer k, 0 < k < n and some enumeration of Lk we are seeking a family {Yi} of irredundant subsets of S with the following property. For every i < k and any subset L of Li (where L1,L2,... is the enumeration of Lk), if fEF (SR)(L), then L(flYj) = L(f) holds for all j > i, and IYi+l - YiI is minimal. In other words at i'th stage we add a minimal number of points to Yi-1 to achieve the desired property. LY', Y. YL '2 L UL X turns out to be such a family i k (for an arbitrary yeS). Proposition 3.4.1 Let S = XSa, where IDI = n and let k be any integer, 0 < k < n. cED nk nk Let {Li} kbe an enumeration of Lk and let {Yi} be a family of subi=l i-1

99 sets of S, where Yl = X andY Yi. U y for all i, 1 Li+1 1 < i < nk - 1. Then the following hold. a) {Yi }k has the property, that given any i, 1 < i < nk, and any i=l C Li, for every fF (S, R)( L), L(f) = L(flYj) holds for all j > i. b) for every i, 1 < i < nk - 1, if Zi+l is a subset of S such that Zi+l Yi and for every L C Li+1, any fF(S,R) (L), L(f) = L(flZi+1) holds, then IZi+l - Yil I Yi+l -Yi!' Proof a) The fact that the family {Yi} satisfies property a) follows directly from part e) of Theorem 3.4.1. b) It follows from Lemma 3.4.1 that Zi+l has to contain at least one point from every equivalence class of Hi. To prove the minimali+l ity of (Yi+l - Yi) then, it suffices to show that for every zcYi+l - Yi' [z] n Y. = Y. Since XY contains exactly one point from every II i+l i+l equivalence class of I, this will show that every point of i+l (Yi+l - Yi) is the only point from its T equivalence class in Yi+l' i+l and thus at least as many as IYi+1 - Yil points have to be added to Yi to achieve the desired property. Let zEY+1 Y. -4 -Y~1 il i~ i+l z EXY z = y for all acD-Li+1. i+1l z Ai =~ Z4 < for V = 1,...,i. From Definition 3.4.1 then it follows that for every Zs(1,...,i) 3 an lczD-L1 s.t. z y Y. But zR

100 since z = ye for all ecD-Li+l, this implies that for every T X an alte(D-Ll) n Li+l s.t. z i# y~. (It can be checked easily that since Ll # Li for all L, (D-L ) (l Li is nonempty.) i+l Z 1+1 Suppose 3 an sEY. s.t. P (s) = P (Z),, i.e. ss[z] S t. This implies s = yet for all cED-L,. But sa = za for all aELi+l and by the above argument 3 an ates(D-L ) n L s.t. so = zi # y0 l. So indeed for every zcYi+l - Yi [z]) nYi w hich completes the i+l U proof. It follows directly from Proposition 3.2.3, that for any function i f from S to R, L(f Yi) L= 'L(fIL) We remark that the {Yi} family of Proposition 3.4.1 has the following property: for any i and any L C Li, given any j i and any function fyF (L), there is a unique extension f of f to S with location L. We also note that given k, 0 < k < n constructing {Yi family of subsets of S as of Proposition 3.4.1 is a way of building up Yk set, since Y -= Y nk k Suppose that although the function f on S is not known, an upper bound on the size of its location is given and equal to k, where 0 < k < n. Then if f lY is known we find L(f) and f itself without needing any more information. That is guaranteed by parts e) and f) of Theorem 3.4.2. This is also the manner in which Yk sets will be used

101 for model building. Another way to proceed would be to experiment on Y1, then Y2, etc., eventually finding the desired function and its location. Although in particular cases it might be possible to quit at some earlier stage, before Y Yy is reached, this is not the case in general. nk k Essentially, this results from the fact that for Ll U L2 D L3, and f any function from S s.t. L(f) C L3, although L(fxI ) lU L(f4E )I = L(fI4 u4 )L(f) = )L(fX ), the above con1 2 1 2 3 tainment may be proper. Thus it is not sufficient to choose enough elements of Lk to cover D, we might need them all. We will now illustrate the construction of Yk sets by an example. Example 3.4.2 Consider S = {0,1}3 and y = (0,0,0). Then Y 0 = x = {(o0,,0)} 0 Y Xy Xy Y = {(0, 0,0),(1, 0,0)} U {(0,0,0),(0,l, 0)} {(0,0,0),(0,0,1) } = {(0,0,0), (l,0,0), (o,l,o), (0,0,1) } Y2 = X UxU JXC = {(0, 0,0),(0,, 0), (1,0,0),(1,,0)} ut 2 {aPU21 {cxcx 31aa2} {%c3} {(0,0,0),(0,0,1), (1,0,0),(1,0,1)}1U{(0,0,0),(0,0,1),(0,1,0),(0,1,1)}= {(0,0,0),,(o,l,o) (,0o,o0),(l,,o ), (0o,o,),(l,0,l),(0,1,1) } YY = S yY Y Y C YY holds. o We would like to remark now on a relative size of Yk sets. It follows from part b) of Theorem 3.4.2 that if all m 's are cx 7

102 n-l same and equal to m, JYnlJ = L()(m-l) = in N~i=)( ) n- = (m-l)n. 1- (1- ) becomes very small. Some example relative sizes of YY1 m n-i aree given in the table of Figure 3.4.2. In the next proposition we will show that every superset of YY n-1 is irredundant. This result will be used in later chapters. Proposition 3.4.2 Let S =, where ID| = n. Then for any ycS and any X D Y-i' X is irredundant. Proof We recall that YnY = {slscS and d(s,y) < n - }. Since ID =- n, for every sES, d(s,y) < n holds. Also since IS > 2, S - Y = {sIsS and d(s,y) = n} = (S -{ya}) = XC= C, where -1OtD aEDa Ca = S - {y}, V aOD. Thus S - Yn-l = C is Cartesian, Ca C S, and by Lemma 2.4.1 every X D S-C = YY is irredundant. This completes n-' the proof. Remark In case S is not Cartesian but is a set difference of two Cartesian sets, S = X S - XCo, where IS.-Cc >~ 2, for all a the folaEOD cED lowing observations are in order. 1) For every y><(S a-C) the following hold.

103 S= X S I = m, for all EcD. IDI = n =5 aEDe m 3 5 6 7 8 IY< 211 2101 4651 9031 15961 ISI 243 3125 7776 16807 32768 IYyn! n --- — i.868.672.598.537.487 Figure 3.4.2: Relative Size of YY as a Function of m. n-1

104 a) for every L C D, such that ILI < n, X, ' S b) for every k < n Y F S (where 4, Yk are subsets of; XS as czD defined before). 2) Theorems 3.4.1, 3.4c.2 and Proposition 3.4.1 essentially hold for S as above, except for obvious minor changes. Fn

CHAPTER IV LOCATION INFERENCE 4.1 Introduction In this chapter we will deal with the problem of location inference for functions from a structured domain S to a codomain R. It will be assumed throughout, that all sets involved are finite. Thus S, the index set D, which S is structured over, and R will be finite sets (<IR > 2). It is often the case, that the function involved is known on some proper subset of its domain only. This happens for instance, when the functional values are obtained through experimentation and so practical limitations on the number of experiments conducted are present. Given a function f from a subset X of S to R, the "actual" function f from S to R (not known) is an extension of f to S. Relative to a probability space defined, for every location L of f, we find the probability that L is a location of f. This probability reflects the confidence we have in L being a location of f. We will discuss here the properties of confidence function and its dependence on parameters (location, upper bound on location sizes, a subset size, etc.). We will show that for any two irredundant domain subsets X1 and X2, where X1C X2, and any function f from S, confidence in the location of fIX2 is at least as large as confidence in the location of 105

106 fix1. It is in this sense, that confidence is nondecreasing. We will also talk here about an average or expected confidence on a subset X of S. This will be formally computed as an expected value of a properly defined random variable on X. Finally we will describe how to make predictions of f to S or some proper subset of S, given knowledge of f on a subset X of S. We will then discuss the relation between the size of the predictive range and the confidence we have in predictions made. 4.2 Confidence in an Inferred Location In this section we will define the confidence function. The probability measure chosen, will be the one making every function from S to R equally likely. This reflects our assumption that "everything we have not seen yet" is equally likely to happen. We will then analyze the most important properties of confidence function introduced. We will use the notation established in previous chapters. Let <F(S,R),2 R) P> be a probability space, where 2F(SR) is the power set of F(S R) and for every As2 (' R), P(A) = JA I. (SIR) IF(SIR)I Definition 4.2.1 Let X C S and let f:X + R. Then for any L C D, any integer ub such that 0 < ub < IDI a) CONFf(X) (CL,ub) = P(actual fcF (CL, )Iactual fcEf(X) (,ub)) (S,R) - (SR) (S, R) b) CONFf(X) (L ub) = P(actual fFF (L,- )actual fcEf(x) (),ub)) D (SR) u(S)R) (SR) When ub = n = IDI we will denote CONFS( )(csL,n) by _fSR) (SR) (S)(SXR) CONF(S R)(CL) and similarly CONF(S R)(LRub) by (S )(L).

107 We note that CONF,R(C L) P(actual factual f) and f(x.) (SR) acu) a CONF(() (L) = P(actual fF( R) (L) lactual f(SR) CONFR (S,R),R ' Proposition 4.2.1 Let X C S and let f:X + R. Then for any L C D, IE(S, R)(C L,ub) I if E (S,R)(.ub) f (ES,IR) a) CONF(X) (CL,ub) = a (S,R) - 0 otherwise (S R)(L,ub) f(X) if E (~,ub) J~~ ~~f Eub (S,R) CONFf(X) (L,ub) = E(s R) (ub) (S, R) 0 otherwise b) In case ub = n and 3 an LEL(f) such that L D L CONFf(X) (CL) = IRI-{(ISI-IPL(S)I) - (iXI-IPL(X)I)} (SR) In case ub = n and LcL(f) CONF (X) (L) = IRI-{(s -IPL(S)!) - (I-IPL(x) I) } (SR) Proof a) It follows directly from Definition 4.2.1 that CONFf(CL,ub) = P(actual fsF(CL) |actual fE f(.,ub)). In case E (-,ub) = ~ the above is clearly O. Otherwise we employ a well known formula for a conditional probability and

108 CONFf(c Lb) P(actual feF (CL) and actual fEE (,ub)) P(actual fEEf (,ub)) P(actual feE (fC L, ub)) Ef (CL, ub) F P(actual f Ef(~,ub)) lEf(,ub) I/IFI The last equality follows directly from the definition of P. Similarly we derive the formula for CONF(Xs) (L,ub.). b) It follows directly from part a) that Nf(X) ) IEf(X) (C_ L) I CONF (CL) = IEf(X) I Obviously since there are iS-XI = ISI- IXI points of S-X, there are IRJS X I XI possible extensions of f to S. It follows from Theorem 3.3.1 that with L as assumed IE(s(X)(C L)I = RI LL (S, R) There are I PL(S) I I PL(X) I blocks of T in S-COMPL (X) and I RI values may be assigned to every such block. Thus I TP(s) - i PL(X) I CONF( (CRL) = and the final expression for CONF (CL) readily follows. To compute CONF(s(X) (L), where L~L(f) we use part a) of Proposi(SR) tion 3.3.3 and just proven result. a Remark 1) We note that for an irredundant subset X of S and any function f:X + R such that L = L(f) and ILI = ub CONF(s(X) = 2) For any two functions fl and f2 from X to R, if L~L(fl) and LsL(f2), CONFS(R) (L) = CONF( (L) holds, 0 (S,R) (S,R)

109 Proposition 4.2.1 will be used essentially in the following way. Having observed f on X, for every LcL(f) we will compute CONF R)(L,ub), (SR) where ub is a given bound on location size, known or assumed a priori. When IL(f) I > 1 we might choose the location with highest confidence as a location of f and the corresponding confidence gives us simply an idea as to how good our choice is. When IL(f)I = 1 we are dealing of course with the unique location of f. We note that if S is irredundant Ef(X,) = 0 when LI > ub. (SR) Also E(f(b)(Lub) = f(X) (L) for L with ILI < ub and arbitrary S. (SR) (SR) We will next show that confidence is nondecreasing with the decreasing upper bound. This should be intuitively obvious, for as an upper bound decreases we decrease the number of possible candidates for our function. Proposition 4.2.2 Let X C S and let f:X -+ R. Then for any L~L(f), any ubl, ub2 such that Li| < ub2 < ub (f) f(( CuNf(X) (-ub) CONF(sR) (L,ub1 ) CONF(S,R) (Lub 2 ) Proof Since L < ub2 u b holds E (L,ubl) = E (L,ub2) = Ef(L). Thus to show the above inequality, we just need to show that IEf(',ubl)l > IEf(',ub2)1 (see Proposition 4.2.1). ub1 > ub2 implies that Ef(.,ub2) C Ef(.,ubl) and the above inequality clearly holds. 0 Our next result will be following. Given any two irredundant subsets of irredundant S, X1 and X2 such that X1 C X2 and any two functions fl and f2, where fleF(x R)f2cEF(x R)' and fl = f2X1 holds,

110 the confidence in L(f2) being a location of actual function is at least as large as confidence in L(fl) being a location of actual function (provided upper bound condition is met in both cases). So as we go on experimenting the confidence will never decrease. Before we state and prove it, we need to establish some auxiliary results reflecting the relations between cardinalities of projections on X1 and X2 sets. Lemma 4.2.1 For any X1 C_ X2 C S and any L,L C D, where L D L IP(cx)I> - IP(x, IP jL(X2)1 - IPL(X) I Proof IPj(X2)I - IPL(X1)I = IPL(X2-{xI X2 and 3- a yeX s.t. yIIx})I = I P~(jX-{U [xI X [xx] n X,}) I IP~(X2-COMPLX 2 (X))I =P(Y L IL Similarly, I()I-IPL() = I PL(X-CO L ( )) = P (YL) I. Since ~L D L. Y^ D Y holds and so I P(Y) I P_ (Y t then S L- L L L PL(YL) But then I P^(Y) I > IPL (Y~) implies that I P~(Y~)I Z IP L) iL which was to be proved. Corollary 4.2.1 For any X,X2 Q S and any L,L C D, where X1C X2 and L D L, the following hold. a) IS-XIl - IS-X21 > ("PL(S) l - IPL(X1)I) - (IP(S)I - IP~(X2)I) b) (IPf(S)I - IP_(X1)I) - (IPL(S) l - IP~(X2)) > (,1 fP '- _ I I - ' _ /I D c' _ - I I (X2 1)

111 Proof a) Since X1 X2 S, -X1 I - IS-X2 I X211 = xX2 I - Ix 1 I IPD(x2)I - IPD(x,) I. By Lemma 4.2.1 PD(X2) - I D(X1) I I PL(X) I - PL(X1) I holds. Also by the very same lemma IP(s) - I P(X) I > IPL(S)I- IPL(X2) I. Adding the above inequalities we obtain x2!- IxI! + lp~s)I- IPx>l2)I I1 P(s1- IP(xj l which implies x 21 - Ix I ('L(S) - PL(xl),>) - (I P(s>)I - IP^(X I)|, which was to be shown. b) We note that the left hand side of the inequality is simply equal to I PL(X2)I - I PL(X1) I and similarly the right hand side of the inequality to IPL(X2)I - IPL(X1)Il So the inequality of part b) is simply another form of the inequality of Lemma 4.2.1. We are now ready to state and prove next theorem. Theorem 4.2.1 Let X1,X2,S be all irredundant, where ~ # X1 C X2 C_ S holds. Let f2:X2 + R and let fl = f2X1. Then with L1 = L(fl) and L = L(f2) (1) CONF( I L1 ub) < CONFf( X2)(L2,ub) holds for any integer ub, (S9R) (SR) 2 O < ub - n, provided that if IL11 < ub holds then IL21I ub also holds. Proof We first note that since X1 and X2 are both irredundant, L1 C L2.

112 If IL11 > ub then clearly IL22 > ub and both sides of (1) are equal to 0. So assume |L,I < ub and IL2! < ub holds. Then Ef l(XI)(,ub) i ( -2- (s R) 9~(S,R) and Ef2(X2) (.,ub) f. Hence we need to show that (SR) IFf'(Ljl < ____( L2_ __ (2) S (L holds lEfl(,ub)f Ef2(.,ub)| or equivalently that IEf1(L)[ |Ef 2 (L2) (3) < holds. U E1(LC f) K, Ef2(cI L) L L! ILI =ub _ I =ub L DL LDL2 Since L2 L, {L = ub and LL1} D { IL = ub and LDL2} and so YJ Ef (CL) D U Efl (CL). Z L IZI| Ub I I=ub LDL1 LDL2 To prove (3) then it suffices to prove that |Ef1(Ld) I Ef2(L2)I () U (CL) I U Ef 2 (C L)I ILI =ub IT I=ub LDL2 LDL2 From now on we will denote the set {L I|L| = ub & 'LDL2} by L. We note that (4) holds if and only if LE 1(( L) UE c L (5) > _ — holds. ET, (L,) - Ei2 (L2)1 Since Efl(L1) =Ef1(CL1) and L C L2, clearly Efl(C Ll) C.h_ Als s, Efl(6L2) holds. Also since L2 = L(f2), E(S R) (L,) = EfR (' L2)

113 To prove (5) then it suffices to show that | E 1g ( L| |Ef 2(~ LY) (6) - > holds. Ef I(CZ L2) |E 2(L,) I We note that for any irredundant subset X of S (irredundant), any f:X + R and any L,L C D Ef(X) (C_ L) n E(X ( L) = E C (LnL)). Also for any family of finite sets A1,A2,...,An IUAil = IAI + (IA2I-IA1nA2I) + (IA31-IA3 A I -IA3f A2 I+IAln A2( A31) +... holds. Let Li,L2,..., Lk be an enumeration of L. Then I 9JEf'(C)= I Ef'(C1) I + (jEf'(Cq 2) I - IEft(C (TnT2)) I) + (IE '(CL) I - jEf '( (Y31)) I - IE 1(C (3flL2)) i + IE '(C- ',n'2ft3)) I) +... = A1 + A2 +A3 +..., where each Ai is of the form A. = IE'l(CZi)) - IEf1(c Lp) + LIEf1(CL )IL Pa~i qi for some index sets Pi and Qi. For every pEPiL2C Lp; Li and for every qEcQiL2 C L. holds. Ii", = ub for all i and i D L2, i. every - - Li i - 2' ' To prove that (6) holds then, it suffices to show that for every i pe- p qeQ q (7) PzPi qzQi - > IEf 1(Q L2)! IEf- 2(L)I- -IE 2(C Lp) + IEf 2(C L )I pEP. qeQi q 1 1 IEf2(CL2) I We will now show that if Qi # ~, then for every qeQi

114 - q > - q IEf'(C L2) I Ef2(C_ L2) We need to show that IPL (S)I - PL (X1)I IPL (S)| - IPL (X2)I 1R1 q q > q q L2() - I PL (X1) I PL2(S) - I PL2(X2)I IRI 2RI Since L2 C Lq V qEQi and X1 CX this follows from part b) of Corollary 4.2.1. So to prove (7) it suffices to show that for every i (8) _ _ _ - IE 1(C L2) I IE 2(C L2) I holds. If P. -=,(8) holds by part b) of Corollary 4.2.1. So assume Pi i f. We note that since for every pEPi, L1 C L2 C L holds, E1(C_ Lp) # P and E 2(C L ) # for V pEP. Thus!Ef(C L ) | and ~~~~~~~~p p PEP. ZiE 2(~ L ) | are both greater than 0. Also as can be easily seen PPiP. both nominators of (8) are non-negative, while both denominators are strictly greater than 0. If RHS of inequality (8) is equal to 0, then the inequality clearly holds. So assume it is greater than 0. Then to show that (8) holds it suffices to show that fi,(ir) ( - El (CL )CL) (9) -lholds. IEf2(C-L)I - ZIEf2(C Lp)I jEf2(C L2)I PEPI

115 We will now show that IEl (CL )J I) F- P I (Ef _ L2I (10) - - - holds. ZIEf2(C L ) I IEf2(C L2) I pEP. To show that, it suffices to show that for every PEPi lEf(_ (CL) | Ef (C L 2) (11) I ---L_ ) -p > is true. IEF2(C L )I 1E2( L2 ) But (11) follows immediately from Corollary 4.2.1, since L2 C Lp for V PPi and X C X2 Thus (10) holds and to prove (9) it suffices to show that JE'(C L.)l - EE f(c L pp) ZIE'(C P)I PPi..PPi (12) P > 2P {E C< L >{ - ZEt2( L ) ErCL)I pEP. pciP. 1 1 Inequality (12) holds if and only if YL Ef|(C LP)I f'(c-i) PEP (13) - holds. JE2(C L ) ZJE2(C L )I pciP. This follows from Corollary 4.2.1. (We show it for every pEPi.) So (1) of Theorem 4.2.1 holds, which was to be proved. O We remark that for X = ~, CONFf(X) (L,ub) can be interpreted as WS, R) an a priori confidence in L being a location of actual f, under given upper bound condition. We will denote it simply by CONF(S R)(L,ub). We will now show that for an irredundant S and any L ~ D, any irredundant subset Y of S, Y $ ~, any function f: Y + R such that

116 L = L(), CONF (L,ub) CONF(Y) (L,ub). In other words having seen (S,R) (S,R) a function from Y with location L may increase our confidence in L, but will never decrease it. Proposition 4.2.3 Let X be an irredundant subset of irredundant S. Let f:X + R and let L = L(f). Then for any ub (1) CONF (L,ub) COF(X) (Lub) (S, R) (s, R) Proof When X = C (1) clearly holds. So we assume X # %. If ILI > ub, then both sides of (1) are 0 and we are done. So assume ILI < ub. IF( R) (L)I CONF(L,ub).= 9. Since F (L) C F ( L) and IF(.,ub)I (S,R) - (S,R) - F (,ub))!IF (CL)j F(S,R) ) F S,R)(L), CONF (L,ub) (SR) L) D (SR) (SR) U F(SR)(L)I(S, R) L L JLj ub We will denote {LjL ) L and ILl = ub} by L. Since CONF'(X) (L, ub) = f(L jJEf(L) I LEL to prove (1) of Proposition 4.2.3 it suffices to show that (1) F(CL) < IE (L)I holds. IJ F(L) IU Efi(L) LouL tZLL By analogous argument as in the proof of Theorem 4.2.1 it suffices to

117 show that for any LTEL and any index sets Pi, Qi where for every ePi, L L Lp C Li for every q~Qi L C Lq F(L)- - IF(C Lp) l + IF(C L )I Z-d _ q (2) q IF(C L) I IEf - I Ef(C Lp) I + Z I E( Lq) PEP qgQ p.................... 1holds. Ef (C L) I We show that for every qEQi (if Qi # P) JF(C L )I Ef(CL ) (3) -- q > q!F(C L) | IEf(C_ L) I IPL (s) I P (S) I- PL (X) 1 1 IRI q IRI q q LHS of (3) equals P(S) and RHS of (3) equals L(S) PL(X) I IRI IRI Since L D L, V qcQi PL (X) l > iPL(X) and hence (3) holds. q Thus to prove (2) it suffices to show that IF(CL)I - F(C LP) IE(C Li) - IE(C LP) p-P peP. (4) > holds. IF(C L) I IE(C L) Again it is clear that both nominators in (4) are nonnegative while both denominators of (4) are positive. Also I |F(C L )I and IEf (C L) I are both positive. pEP. peP. i i We will now show that E IF(c Lp) I (5) - > holds. Ef (C Lp) Ef(C L) | pePi

118 It suffices to show that for every peP I F(C L ) IF| S L) (6) P > IEf_ L )| IEf(C L)I IPL (s~l PL(S)I But |RI P > | I I L holds I L (S)j - IPL (X)I - -PL(S) PL(X)I RI pRI since LP DL implies PL (X) L > I PL(X) I So (5) is true and to prove (4) it suffices to show, that IF(F(IL )- Ef(C9 )I F- l)Ef(C_ L ) pep PE p (7) > holds. 1F(C L Z) IEf( L ))I (7) holds if and only if IF(C i)I | gf(C_ Li)I (8) > holds \ IF(C LP)I E | Lp) )I i i if and only if for every pEPi F(C Li) I BE ( i) | (9) > - holds IFSC Lp) ) IEf(C Lp) I if and only if I Pr. (S) (s) - P () (10) > holds. (10) -IPL (s) I I P (S) PL (X) I. IRI P |RI P P But since Li _DLp, I PT.(X)I > IPL (X)I and so (10) holds. This 1 P completes the proof. 03

119 Remark We remark that Theorem 4.2.1 holds for arbitrary X1,X2 and S (rather than irredundant) in case ub = n and LlcL(f l) L2cL(f2) are such that L 1q L2. This follows easily from Corollary 4.2.1 (part a)), since _ f~I PL (S)- I PL (X1)I L > =RI IRI CONF(S R) (L1) = and;~ TSI - Ix! IPL (S)l IPL (X2)I f2 - IRI CONF(S R)(L2). RI IRI ISI - IX2 We will next show that for any two functions f and g from X to R, if L(f) C L(g) holds, then confidence in L(f) being a location of actual function is not greater than confidence in L(g) being its location. Thus as the complexity of the function increases, so does the confidence. By complexity we mean here simply the size of the location of the function. The above is made precise in the following. Proposition 4.2.4 Let X be an irredundant subset of irredundant S. Let f and g be functions from X to R, where L(f)C L(g) holds. Then f(X) g(X) (1) CONF (L(f) CONF (L(f)g) (L(g)ub) holds for any integer ub, O <ub < n, provided that if IL(f) I < ub holds then so does IL(g) < ub. Proof Let L(f) = L1 and L(g) = L. If IL1I > ub, then IL2I > ub and

120 both sides of inequality (1) are equal to 0. Thus (1) holds. So we assume that IL11 < ub and IL21 < ub hold. Then -Ef(X ) CONFf(S) (Ll,ub) = and ILU El(X) (C) J L LI =ub LDL ~~~~CONFg~~~ ( i) ) U LEg L IzlL |L.|,=ub L p L2 Since L2 DL1, IPL (S)I I 'L2(X) I PL (S) - PL (X) I. This follows from part a) of Corollary 4.2.1, where X1 = X2. Thus by Corollary 3.3.2 IEf() (L1)I < IEg(x (L2). 2 2 Since L2 )L 1C'L _L and |L I=ub } D {L t 2 and IL =ub}. Thus I UQ Ef(X) ( f(X)(C ) = I Eg(X) (C L) L I=ub L I=ub IL =ub LDL L L2 L _L2 So clearly (1) holds, which we were to prove. U We note that if X and S are arbitrary but ub = n, Proposition 4.2.4 still applies. Remark 1 In Lemma 4.2.1 and Corollary 4.2.1, when X1 and X2 are Yy and k1 YY sets respectively, (IS = m for V acD) the containment of the k2 locations is not a necessary condition. Rather than assume that L - L holds it suffices to assume that Ul1 2.LI

121 This follows from the fact that for any Yk and any L1,L2 with [LI =IL21'L (Y:)] = IPL (Y:)[' 21,1 kl I L2 k Similarly, in Proposition 4.2.4 if X is a Y: set, it suffices to assume that IL(f)I < IL(g)I holds. Remark 2 1) We note that for any subset X of S (S not necessarily irredundant) and any function f from X to R, if D is a location of f, then CONF (S R)(D) = 1. First we notice that if DEL(f), then D is the unique location of f. But then this implies that every extension of f to S has location D and the above statement follows. 2) Given an upper bound ub, ub -< n - 1, and any function f from -'yY ) YY to R, such that IL(f) I < ub, CONF [ub (L(f),ub) = 1. This follows ub (SR) f(YY ) from the fact that for any L?L(f) such that IEL < ub, E(Sb R) =u (see part e)of Theorem 3.4.2). 3) For any XC S and any f:X -+ R, any LEL(f), f(X) _ _(Lu) __1 CONF(sR) ub) RiSX 1 provided IL < ub. This follows from Corollary 3.3.2 and the fact that Ef(X) (,ub)C Ef(X) Clearly IEf(X) I = IRII|S-X| We will illustrate the above results by an example. Example 4.2.1 Let S = {0,1,2}} and let X1,X2 be following subsets of S. X1 = {(0,0,0),(1,0),(,,),(1,1,0),(1,1,1)} and X = X U {(2,1,1)} = X1 U {(2,1,1),(1,1,1)} = X1 U C.

122 X1 is clearly irredundant as a minimal independent set. X2 is irredundant by Proposition 2.4.4. a) Consider f: X1 + R, where R = {0,1,2} and f is defined by a table of Figure 4.2.1. Then L(fl) = {a2 }. With ubl = 3 and ub2 = 2 PO (S) - IPa (X1) Ct2 2 33-2 1 I I (X) (X 1) I IS-XI11 327-4 = 323 f (X1) f (X1) f1(X1) IE (',C 2,c2}) I + IE (C 2{2,3})I - IE (C '2}-) I = 9-3 9-3 fl1(X1) 3 1 3 + 3 - 3 = 3(2-3 -1). Thus CONF(SR) (L(fl),ub) = 3 =22 (S,R) 323 322 f (X1) _3 1 and CONFSR) (L(f1),ub2) 3(235-1) 23-1 Clearly (S3,R) 3(2.35-_) 2.1 5_l fl(Xl) f l(X1) CONF(S R) (L(f ),ub2) < CONF(S,R) (L(fl),ubl). The above illustrates Proposition 4.2.2. b) We shall now illustrate Theorem 4.2.1. Let ub = 2 and let X1,X2 be as above. Further, let f2 be an extension of f to X2 given by Figure 4.2.1. f2 (X2) Then L(f 2) = {c2 }. We compute CONF(S,) ({a2},2). e L(f) f 2 CN F (S.) f2(X2) f (X s) x(X2)) IE (-,2) 1 = IE ( { a2}) | + |E (C {,a3}) - f2(X2) IE ({a2}) = 39-4 + 39-3 - 3 = 3(34+35-1).

123 x f (x) fl: X1->li (0o,0,0) (1,0,0) O (1,1,0) 1 _(1,1,1) 1 x f2(x) X 2R (0,0,0) f2 X2+R (1i,o,o) o (1,1,1) 1 (2,1,1) 1 x g1(x) gl: X1+R (0,0,0) O 1 1 (1,1,0) 2 (1,1,1) 2 Figure 4.2.1: Function Tables of Example 4.2.1.

124 f2(X2) 3 1 Thus CONF ({a2 }2) = -, while (S,R) 3(34+35-1) 34+35-1 f (X1) f (X) CONF(S R) ({a 2}'2) =. Clearly, CONF(S R) (L(fl),ub) < 2,3-1 (SR) f2(X2) CONF(SR) (L(f ),ub) holds. c) We will now illustrate Proposition 4.2.3. We compute CONF(S R)({a2},2), an a priori confidence that actual function has location {a2}, given that the cardinality of the location of all possible functions is at most 2. IF(SR)(a I CONs {, 2)...... IS(s,)(-,2) 2 (SR) 2 IP (S)l I a I - IF(S R ) = R- 1 = 33 - 1 IF(sR)(*'2)1 = IF(SR) (C {al,'2})I + (F (S,qR)(C- { 3l, 3})I - IF(S,R)(-{a1})I) + (IF (S,R) ( {2' 3}) I - IF(S R)(C {a2}) IF(SR)(C {3})I + IF(S,R)(cI = 39 + (39-33) + (39-33-33+1) = 3.39 - 3-33 + 1 33-1 33 1 So CONF {, 2= {e2 <' 2) = SO CONF(S o,$2}) 39 3-3~ 33+1 310-34+1 37-3+3-3 1 f1 (X1) 2*35-1 CONF ({a2 },2). d) Finally we will illustrate Proposition 4.2.4. Consider a function gl from X to R, as given in Figure 4.2.1. L(g1) = {a,a2} D {a2} = L(f)). With ub = 2 as was computed in part a) of this example

125 fi(X) 1 CONF(S R) (L(f1),ub) 5-1 2'3 -1 g (XI) IE 1(x1) ({a' 1,2}) 1 I E ({a1,a2}) I CONF(SR) (a '1,2 }'2) = g, (x~~ ~, (x,) 2~ 2(a~ ~ ~~1 L {a -2 f (x ) g (X1) So clearly CONF(sR) (L(fl)ub) < CONF(s,R) (L(gl),ub) holds. We will now discuss the notion of average confidence for a subset X of S. As will become clear later, this is essentially motivated by the desire of a modeller to choose a domain subset to experiment (or generate the data) on, based on expected confidence on this subset. Relative to an upper bound ub, we define the average confidence on an irredundant subset X of irredundant S (denoted by ACONF(S R)(ub)) in the following manner. Given ub, let Zub be a random variable, ZUb:F(s,R) -fR, defined by Zub(f) = CONF(sR) (L(f X),ub). (S, MR) jx) Then ACONF(SR) (ub) = E(Zb Ub) = P(flub)Zb (f). When ub = IDI, we will denote ACONFX(R)(ub) by ACONFX,R)o Proposition 4.2.5 Let X C S, where X and S are irredundant. Let ub be an integer O < ub ~< I(I. Then (1) ACONF~S R) (ub) = IZ)E(L(f))) (/-fZ R.) ( ub) (xR) (. ub)

126 Proof 2) ZP(flub)CONFfIX(L(flX),ub)= f~F CONFfIX(L(fIX),ub). F(s,R).,b)~ ub) (S,R) (b,ub) We note that every fF(S R) (-,ub) is an extension of some fYF(X R) (' ub). Actually, F(SR)(-,ub) = Ef(,ub). /RE:F (-,ub) (X, R)( Thus IF(S R)( ub) =Ef(,ub)b) fcF (-,ub) (X,R) We also note that for every fF(X R)(.,ub) and, any f,g EE - ub), CONFfIX(L(fIX),ub) = CONFg IX(L(gX),ub). So L CONFf I(L(f X),ub) = CONF (L(), ub) E(~,ub) = f6F (.,ub) fFx, (',ub) ~ (S,R) (X,R) Z EI |E(L(f))j. fEF(x,R) (-,ub) Equality (1) clearly follows. 0 We next show that average confidence is nondecreasing with an increasing size of the subset of S. Proposition 4.2.6 Let X1,X2 be irredundant subsets of irredundant S, where Xi C X2 holds. Then for any ub ACONF (S R)(ub) < ACONF( R)(ub) holds. Proof The above follows immediately since for every fCF(S R)(,ub),

127 fiX1 fix CONF (L(fiX ),ub) < CONF (L(fiX2),ub) by Theorem 4.2.1. [1 Next, we will give some lower bounds for average confidence. Before we do that however we prove the following. Lemma 4.2.2 Let S be Cartesian, S = X S Then for any L,L2 C D with ecD L1 C L2, IF(s,R) (L1)I ' IF(S,R)(L2)im Proof Let IL1I = k. If k = n, then L2 = L1 and we are done. So assume k < n. Also we assume L1 L L2. It follows from Theorem 3.4.2, that there is a 1-1 correspondence h between F (SR)(LI) and Fy (L), where h F(S R)(L)) + F (L1) ((ky R) 1 ( 1 (Y, R) is defined by h(f) = flyy. k ' TL Since IL21 > jLj = k, COMPLs2(Yk) $ S. It follows from Remark 3) after Corollary 3.3.3, that for V feF (L ) there exists an exten(YkR) sion of f to S with location L2. This implies that IF(S,R)(L2)I > feF ( (R)(L2)I > IF(S) (L )1 which was to TE F ( nS) ' (YYIR) (YY,R) k be proved. Proposition 4.2.7 Let X be an irredundant subset of S = X S, where |DI = n. te D Then a) ACoNFXe 2 1

128 b) for n > 2 ub and ISj = m, V otCD Z IF (L) I IE (L) I ACONF, R)(ub)> ILI=ub (ub+l) (ub) IF(S,R) (LUb) I where fL is any function in F(X R)(L) and Lub is an arbitrary subset of D with ILUbl = ub. Proof a) FU E implies IF I f I-IF 1 a) F R) (S,R) i (S,R) implies SF(,R)) I (X,R) fEFx (XR) since for any fgEF(R) IE SR) I = IE SR)I. Further FXR) = U F(X R)(L). It follows then from Lemma 4.2.2, that Lz2 IF(X R) I< 2n ~ IF(XR) (D)I and so that IF(S R)I I E(SR) IIF(XR D) |2n Now ACONFX - 1 Z CONflXf(L(fIX)) (S,R) IF (S,R) I fEF(S, R) F1 CONF (L(f)) IEf I> 1 1 Z 1' IEf = IF (S',R)I fF(XR) IF(SR)I fF(XqR) D) IEm.jF (D)I (X,R) M IF(s,R)I ACONFI Ef I FX R) (D) I 1 So ACONFs > - > (S,R) IEf I IF(XR) (D) I 2n b) Since IS I = m for V acD and S is Cartesian, for any L1,L2 C D with ILI = L, IF (SR)(L1) = IF(S,R) (L2)' For n > 2ub (i) s holds for every i ub. It follows from Ijust made remarkis that

131 2I..y 1 1 CONF (lotc)a -- and CONF(SR) ({102}) 28-7 2 2 2 CONF (f= (SR) ({,2}) = 1. For the confidence curve see Figure 4.2.2. YY b) We will now compute ACONF R) for each of the Yk sets. (S,R) k We recall that ACONF R) = IF1 CONF I (L(f)) = 1 Zf (XR)(L)V~IEfL fL (X) IF(sR) IFCDR) (L)I IE CONF (L) = IIF I F(XR) (L)IE (L) E (L), where fL is an arbitrary function IF(sR) I LCD (X,R) from X to R with location L. ACONF R - (IF ()1' = 2 - (,R) 28 (YYj,R) 28 2 ACONFSR) (IF (4F)I(E ).1 )I + (SR) 2 (YR) Fyy + (2)l a Efct})KIE2 (jo1t 2s) I + {F (D)I}IE ({ }) 2~(YYsR) I *a 2(Yk R) We compute |F ({c a})I = 22-2 = 2 and |E l({ct})i = 1 IP (Y,)I IF 2YC, ) 2 I (Y) - IF (4)I-21F ({c }I 1(y y R) 1 2 (YYR) (Yy>R) 2 -2 - 2a2 = 8-6=2 and |E ({c1 1c2})| = 2 = 2. Finally, FD =IY () I-31F ({c }) j-3|F ({a,,a2 }) = (yyR) (YR2 (y 2,R) (Y2,R) 24 - 2 - 3.2 - 3'2 = 16- 14 = 2 and IEfDJ = 28-4 = 16.

132 Thus AoNY1 _1 1 26 ACONF(S = 8 (2 + 3'2-1 + 32'-2 + 2-16) 52 = (S,R) 28 28 2 YY Similarly we compute ACONF (SR)2 To do so, we first compute all the necessary elements. IF ({Ua})I = 22 -2 = 2 and IE l({cl})| = 1 (YY, R) IF ({a1,a}) = 2 - 2 - 2.2 = 16 - 6 = 10 and (Y2, R) IE {13a2 2}({a1,a) I = 1 Finally, IF (D) = 2- - 2 - 3.2 - 310 = 128 - 38 = 90 and IE D1 = 2. So (y YR) 2 _ 218 109 ACONF 2 = 1 (2.1 + 3-2.1 + 3'10.1 + 90.2) = 8 (S,R) 28 2 2 The values of average confidence are tabulated in Figure 4.2.2. 4.3 Prediction Range and Correctness On the basis of knowledge of the function on a proper subset X of S, we would like to make further predictions of the function. In this section we will discuss the manner in which such predictions are made, the range of predictions and their correctness. Suppose then that a function f from X to R is given, where X is a subset of S. For every location L of f, we will predict f to the set COMLPL(X). We shall denote this set in the prediction-making context f(X) - by EXPL (S) (L) and call it the explanatory range of f relative to f(X) - f(X)We will denote the set (EXPL (L)-X) by PRED ( (L) and call it the (S,R) (S,R) predictive range of f relative to L.

131 zIYY 1 1 CONF (and CONF (SI R)({la2}) 8-7 - - and (S) 2 2 CONF f ({ CONF(S,R) ({ 'e2}) = 1. For the confidence curve see Figure 4.2.2. YY b) We will now compute ACONF ( for each of the Yk sets. (S,R) k We recall that ACONF R) 1 CONF fI(L) = f (SR) IF(SR)I fEF IF1 IF(X,R)(L)I IE ICONF (L) IF(SR)I LCD 1 Lf IZF L IF (X, R) (L)II'E (L), where fL is an arbitrary function IF(s,k) I LCD from X to R with location L. 0_ 1 2 1 ACONFs - (IF (() 1 = (S,R) 28 (Y,R) 28 2 ACONI -A (IF I W 1 + IF({) fo (S,R) 28 (YYR) ) I 1(YRIE 2F Y,({oC,a) I. IE {a1. a2 ({o2, a})l + IF (D)I'IE |D) We compute f a F Y ({i })I = 22-2 = 2 and JE 1({'Q }) = 1 (YY,R) IP{, (Y)II iF 3R) 1 2} (Yy >R) 3 4-3 2 -2 - 22 8 - 6 = 2 and JE 1{a12 }({cl, c2})I = 2 = 2. Finally, IF (D)I = 2xI IF R) (4) I-3IF ({c }) I-3lF ({czc2}) = 2Y-,R) (YY -3 16- R)) 14(YY R) 2Y aR) 1 2, - 2 - 3.2 - 3.2 = 16- 14 = 2 and I|% E Dl-2 = 16.

132 Thus ACoNFY1 _1 1 26 (S,R)8 ACONF(S R) = a (2 + 3.2.1 + 3.2'2 + 2.16) 52 = YY Similarly we compute ACONF(S R)' To do so, we first compute all the necessary elements. IF ({a,}) = 2 2 = 2 and E 1({}) = 1 (YY,,R) IF y ({al, 2}) = 24 - 2 - 22 = 16 - 6 = 10 and (YY,R) |E {' (a,'0a2}) = 1 Finally, DI F (D)1 = 2' - 2- 32 - 3.10 = 128 - 38 = 90 and IE DI = 2. So (Y2,R) ACN 2 -1218 109 ACONF(SR) (2*1 + 3*2-1 + 3101 + 90.2) = (S'R) 2 28 27 The values of average confidence are tabulated in Figure 4.2.2. 4.3 Prediction Range and Correctness On the basis of knowledge of the function on a proper subset X of S, we would like to make further predictions of the function. In this section we will discuss the manner in which such predictions are made, the range of predictions and their correctness. Suppose then that a function f from X to R is given, where X is a subset of S. For every location L of f, we will predict f to the set COMPLL(X). We shall denote this set in the prediction-making context f(X) by EXPL( (L) and call it the explanatory range of f relative to L. (S,-R) f(X) - f(X) - We will denote the set (EXPL (L)-X) by PRED (L) and call it the predictive range of f relative to L.

'ZZ'p aOTduIvxjH Jo suoTzj:unj pue saqqe': '**P an (I (axs) (i)ldl - It()(Xii)rldlI) - (Ixi-Isl) S A 0 XA 0 I z ~ t S 9 / Lt7 -I I ((s) (( >AJ I) (s ) NOD I 11'0 0 (T'O'I) I t ~ ~s o (It'o'o) ____ (o'VT') 601, X_ I I ( o'i'o) z_ _of o0 0 (o' '1) _,A (d'S) 4NI V '0 (o )

134 Let f and L be as described. Let f- denote the predicted function f(X) on EXPL(sR)(L). Then we define fL to be the unique extension of f to COMPL (X), namely for every yeCOMPL (X), fE(y) = f(x), where xeX is such that xNly. (See Lemma 3.3.1 and Corollary 3.3.3.) Clearly flIX = f. Remark L f(X) 1) We note that if COMPL (X) = X, PREDf(X) (L) = 4 and so we make no new predictions. This happens for example when L = D. 2) For any two functions f and g from X to R and any L1,L2 such f(X) ( g(X) that LlEL(f)), L2L(g), where L1 C L2 holds, PRED (L1) D PRED(sR)(L2). L L This follows directly from the fact that COMPL l(X)D COMPLSL2(X). 3) We note that COMPL (X) is the largest subset Z of S with the -S property, that for all fE( R)(L), fiZ is unique. (S, R) This follows directly from Proposition 3.3.3 and Theorem 3.3.1, provided IRI > 2. c] f(X) In the sequel we will denote by PCONF(sR)(L) the probability that all predictions were made correctly (when L was "chosen" to make them) and call it the predictive confidence. More precisely f(X) f(X)f PCONF(X) (L) = P((actual function fjEXPL (SR (L)) = flfEE ) f(X) ( Similarly, when an upper bound ub is given PCONF(sR)(L,ub) P((actual function fIEXPLf(X) ) = actual fES R)(ub)) P ((actul fnctin fI EXL ( )(L) f actual f EEPL (s,ub)). In the next proposition we find an expression for PCONF () (L, ub). (S,R)

135 Proposition 4.3.1 Let X be a subset of S and let f:X + R, where fEF(X R)( ub). Then for any LsL(f) and any integer ub, 0 < ub < n, f-(Y) f(x) ([.,ub) E L (,ub). a) PCONF() (L,ub) = ) IEf(X) (.,ub)l f(X) where Y = EXPL(,R) (L). b) If ub = n PCONF (X) L) (S, R)) f(X) (~') IRi (SR) Proof a) Since fcF(x,R)(.,ub), Ef(X) (-,ub) # c and we are not dividing by 0. (See Corollary 3.3.2.) The expression for PCONF f(X) (L,ub) follows directly from its (s, R) definition, when the formula for conditional probability is employed. b) It follows from part a) that f (Y)!(X PCONF (L) = 1 =E ixRI I(LfS -R JEXPLf() (()) - x 1 1, which was to be proved. El RI IEXPLf(X) (L)-XI IR] PREDf() (RL)I It can be easily seen from PrOposition 4.3.1 that the relation between the number of predictions made and the confidence in the made predictions is reversely proportional. That is, the more we predict the smaller the certainty, that we are correct in our predictions.

136 We note that if actual function f from S to R has a location L, then - as described above is the correct prediction of f to?(x) - EXPL (L)S (SR) When actual f has a location L, where L; L holds, however, we are assured of the correctness of our predictions to the set COMPL (X), rather than EXPL(S )(L). That at least those among our predictions are correct, follows directly from Lemma 3.3.1. We will call the set COMPLS(X) in this context the validity range of f with respect to L and denote it by VAL() (L). We will show that for a Cartesian S, VAL(X) (L) is the largest subset Z of S with the property, that for every fEEf(X) (L) f1Z is (S,R) equal to the prediction by f. Proposition 4.3.2 Let X be an irredundant subset of S = Sa, where ISI > 2, Vc fD. Let f:X + R, where IRI > 2 and let L = L(f). Then for any L D L, COMPLL(X) is the largest subset Z of COMPL (X) with the property, that for every fEEf(x) (L), fZ = fLZ, where f is the prediction of f to COMPIL(X) Proof If L = L or COMPL (X) = COMPL (X), the proposition is clearly S S true. So we assume that COMPLSL(X) CO LS(X) holds. It follows directly from Lemma 3.3.1 that Z D COMPL (X). We want S to show that Z = COMPL (X). Suppose that Z COMPLL(X). We show that then 3 a function gEf(X) (L), such that glZ # fLIZ, thus contradicting

137 the properties of Z. Let p6Z-COMPLs(X). (Clearly Z C COMPL (X), since this is the set S S we make predictions to.) We shall distinguish two cases: L = 4 and L i 4. a) L = 4. So COMPL (X) = S. L L Then f- is constant on COMPL (X), say f-(x) = c for V xSCOMPL (X). We define g on S in the following way. For every xE[p]L, g(x) = d # c. (Remember that IRI > 2.) For all other x in S, g(x) = f-(x) = c. Clearly gIZ J f LZ, since g(p) = d # fL(p) = c. (Since L LL(X) gIdosL(X) L (X).) (X), [pS-COM[IPL (X) and so g COMPL f ICOMPL (X).) S S S L S We need to show that gE f(X)(L). Clearly HS.g Since S is Cartesian L g and ISj -> 2,V acD, for every eaL L an x ES s.t. xIL-a p but xcLp. Thus by our definition of g, for every aEL,3 x s.t. x IL P but g(x) # g(p). This implies that for every aEL, _a and thus L is the location of g, which was to be proved. b) L # 4. So jllj > 2. Let p be as above, i.e. pEZ-COMPLs(X). Again we will construct a g from S to R, such that gEf(X) (L), but glZ # fLZ. Actually it suffices to construct an h:COMPL (X) + R such that L(h) = L but hlZ # fLIZ. Then an existence of g as above follows from Corollary 3.3.2. Since pECOMPL (X), 3 x~X s.t. xnLp. Since IH-I > 2 3 an wEX s.t. f(w) # f(x). This clearly implies that wXL-x, since L = L(f). So wL-p. Now since S is Cartesian and IS I 2 2, for every aEL-L a an x ES s.t. x lp but x0fp. We note that all such x's are related to each other and to p by 11. With x as above (xSlp), all xa's are also

138 IEl related to x, and none of the xc's is Tl related to w. It follows then that all x 's as above are in COMPL (X). a S We define h to be the following function. For V ycCOMPLS(X) - [PIPL h(y) = fL(y) and for yE[p]L, h(y) = f(w). We need to show that hE f(X) - in other words that h|X = f But (COMPL (X),R) since peCOrPLL(X), [P]L n COMPLL(x) =, - [p]i n X =. Thus for ~S T1L ~S L V yeX, h(y) = fjL(Y) = f(y), which shows that hiX = f. Finally, we have to show that L = L(h). Clearly IL< 5 h. (We recall that L = L(fL) and so L = L(hlCOMPLL(X)-[p] ). L h COMPLL (X) - -[p] Also since h is an extension of f, L(h) 3 L. To show L = L(h) then, it suffices to show that for every aeL-L, 3 x ECOMPL (X) s.t. x II p L-o but h(x ) # h(p). Now h(p) = f(w). With x-'s as before h(xe) = fj(x ) = f(x) # f(w), which completes the proof. For the illustration of the above proof refer to Figure 4.3.1. 0 In the following example we will illustrate that the number of predictions made is ambivalent with the size of X. Example 4.3.1 a) Consider S Cartesian and L L D. Then XL X. For 2 2 2 any f from S, L(fXy )C L and L(f ) C L2. Thus 1 1 L(fJXL ) L(fjXY ) CONIPLS ' ( COL) = S. But this implies that

139 S = COMPLIs(X) a) L = g([p] d g(S-[p ) = ca]< h~~ ~h[pL ) = f(w) ~~X R'TL LOL2.,L b) Ls X Pigure 4.3.1: Illustration of the Proof of Proposition 4.3.2. /~~~3T /~~~~ [p] i~~~~~~~~~~~~~ 1

140 fIx{ fIxY |PRED 1(L(flX ))W I IPRED 2(L(fX4 )). b) Consider S = {0,1,2 2} and X= {(0,0,0), (1,0,0), (1,1,0), (1,1,1}, X2 = X { (2, 11)} Both X and X are irredundant. 1 2 Let f be a function from S to R = {0,1,2} with H = KS Let fl = fix, and f2 = fiX2. Then L(f ) = L(f ) = {d,. It can be easily verified that f2 f PRED (S R({}) = PRED (SR)({C }) U {(2,0,0),(2,0,1),(2,0,2),(2,1,0), (2,1,2),(2,2,0),(2,2,1), (2,2,2) }. Thus f 2 f PRED 2({ea}) I iPRED ({aO }) The example then clearly illustrates the above assertion. 0

CHAPTER V APPLICATIONS TO DISCRETE TIME SYSTEMS 5.1 Introduction In this chapter we will deal with functions from structured domains, whose codomains have been also structured. We will define a concept of structured model (partial model) of such a function (system). We will be seeking reduced models only. Those models are minimal in a sense to be made precise later. In general, there are many possible reduced structure assignments for a function. When a function domain is irredundant however, the uniqueness of such an assignment will result. Similarly as in Chapter IV we will discuss here concepts of confidence, average confidence, predictive confidence, etc. We will derive the expressions for the above, in case of a Cartesian codomain. We will apply all the results to finite autonomous discrete time systems. In this case the domain and codomain sets are same and equal to the structured state space of the system. The functions involved will be the state transition functions. For those systems we will discuss several strategies, which a modeller might follow during the experimental (modelling) process. The one chosen will depend on his objectives and a priori information available about the system being modelled. 141

142 5.2 Structured Functions We shall first give the definition of a structured function in terms of locations of its components. Definition 5.2.1 (LZ1]) Let S and S' be structured sets, where S C X S and S' C X S. CED aZD' A function f:S + S' is structured by an indexed family of functions {fsIf S:PI (S) + S, I C DBED'}, if f = X,f-P We will refer to a family {IBI3ED'} as above as a structure of f. In general a function f can be structured in many ways leading to different structures of f. For example {IfIBED'}, where I = D for all $ED' is always a structure of f. We simply define for every SED' fs:S + S to be the function fg(s) = PB.f(s). A function f is structured in the sense of Definition 5.2.1 if for every BED' and every sES the diagram of Figure 5.2.1 commutes. In structuring the function we will try to find those structures, which are minimal in the following sense. If {IIjED'} is such a structure, then for any other structure {LSIJED'} of S, if L CI8 then LB=IB, ~VPD'. We will call those structures reduced. More formally, Definition 5.2.2 ([Z1]) A function f with domain S,S C X Sa, is in reduced form if D is asD a location of f. ~ Definition 5.2.3 ([Z1]) A structured function f:S - S', f = X f 'P is in reduced form 3ED' l.....3

143 if every fs is in reduced form. We note that a structured function f is in reduced form if IB is a location of f,, where {I|jaED'} is a structure of f. We will then call {If3sED'} a reduced structure of f. When S is irredundant, every structured f has a unique reduced structure. This structure is given by I8 = L(Ps'f), for all 8 in D'. In case S is not irredundant, but {I|B3ED'} is reduced, I~EL(Ps f), for every BcD'. We will illustrate the above concepts for a transition function of a discrete time system. Example 5.2.1 Consider S = {(0,0,0,0),(1,0,0,0),(1,1,0,0),(1,1,1,0),(1,1,1,1)} and 6 on S to be an identity on S, i.e. 6(s) = s for all scS. S is clearly irredundant since it is a minimal independent set. As can be easily verified the unique reduced structure of 6 is given by Ia = {l }, I = {I } and I = {fa }' O& 1 Ot2 2 3 4 We will demonstrate two nonreduced ways of structuring 6. a) Consider 6e. as given in Figure 5.2.2 a). Clearly 6 = X6c d PI, where ti ei I ={alsa{ 2 } and I = {i }, for i = 2,3,4. This structure is not 1 reduced since L(6O ) = {l}I {a l$2}. b) Consider 6 as given in Figure 5.2.2 b). Again it is easy to check that 6 = X 6 'PI, where i ji t.

144 s PI (s) f ff f(s Pf s P of(s) = f PI (s) Figure 5.2.1: Diagram of a Structured Function. Ix 6 l(X) X 6 4(X) (0,0) O (0,0) O (1j,0) I 1 (1,0) 0 (1,1) 1 (1,1) 1 6 (P (s)) =P (s) 6 (P (s)) = P (s) i i1 1 1 1. for i = 2,3,4 for i = 1,2,3 a),6>b) (o,o,o,o) (1,1,1,1) 7"' (1,1,1,0)) QGr (1,1,0,0) Figure 5.2.2: Illustration of Example 5.2.1.

145 I = {i}, for i = 1,2,3 and I = {alo,t }. This structure is not ( 4 reduced since L(6 ) = {o} } { ac4}5.3 Structured Partial Models We consider here the family F(S S, ) of all function from S to S', where S and S' are structured sets. We will refer to <S,S',f> as a system, where fEF( S)* We shall now explain what is meant by a partial (structured) model of <S,S',f>. Definition 5.3.1 Given a system <S,S',f>, <S,S',f> is a partial model of <S,S',f> if a) S Cs b) S- = S' c) f:S1 + S1. O We will refer to <S,S',f> as a model of <S,S',f> just in case Si = S. We will seek partial models with f = flS1. Definition 5.3.2 <Sl,S', > is a structured partial model of <S,S',f> if <Sl,St,f> is a partial model of <S,S',f> and if f is a structured function. 3 We will then refer to a structure of f as a partial model structure (structure of a partial model). We are going to seek reduced structured partial models, namely partial models of the form <S1,S',f>, where f is in reduced form. The notation we will use here is analogous to the one introduced in Chapters 3 and 4. Thus with S and S' as described before and f a

146 function from some subset X of S to S' Ef(X) E(ss) denotes the set of all extensions f of f (S,S,) to S s.t. fcF(S S') E(XM)(f{L } D,,) denotes the set of all extensions f of f to S, (SS')({L}~D such that L EL(P' f) Ef(X) (C f(X) E(X),(C{Lx} ') denotes the set of all fEE(S(S, ) s.t. for all 8ED' a an L C L with L L(P-f). E(S,,)(,ub} D,) denotes the set of all fEE( ),) s.t. for every 3 a an LcEL(P.*f) with ILI < ub,. Similarly, (XS,) F(XS')({L}szD.) PREDf(X)({} ) ' XISI), ' ' I) (s,s'I) 13cD t' etc. are defined. Again sometimes the notation will be shortened, when the intent is clear. As in Chapter 4 we define a probability space F(S3,S') IAI <F(SS)2 ',P>, where for every AEF(S5S,), P(A) = IF The various concepts introduced previously can be readily extended to structured functions, relative to just introduced probability space. Thus we will define confidence in the following way. Definition 5.3.3 Let X C S and let f:X + S'. Then for any family L = {L }$sD,, where L C D, for all fED', and any family of integers UB = {ubs}z3D,, where 0 < ub < _D CONF S(X) = P(actual fcF (L, )lactual fEEf(X) (,UB When ubg = n = IDI holds for all 8, we will denote CONF (S,?(') by CONF), ( L). (SS') ~~(S,S')

147 Proposition 5.3.1 Let XC S and let f:X + S'. Then for any family L = {L}D,, L C D, V BED', and any family UB = {ub }IzD, of integers, o < ub < IDI, IEf(X) (L UB) I I"~(S'S') ' if E (-,UB) ~ f (Lu IEf(X) (. UB)I (S,S') CONF( (LUB) (, S ' ) E(,') (S,5') 0 otherwise Proof Almost identical to the proof of Proposition 4.2.1. a Remark 1) We note that for an irredundant subset X of S and any function f:X -+ S' such that LX = L(P.f) and IL3I = ub f, CONFu(X) ({L}{ub}) is,CONF(,S') ' equal to either 0 or 1. 2) For arbitrary X and S if L is a structure of f, f:X + S' and UB is such that ILBI < ubs for all L EL, then Eg(X) (LUB) = Ef(X) (L) holds. C Roughly speaking, we showed in Chapter 4 that in case of nonstructured codomain, confidence in structure of functional restrictions had an important property of being nondecreasing with an increasing domain size. When we deal however with structured functions the above property is in general not necessarily preserved. As a matter of fact structure preserving extensions do not always exist in the structured case, as they do in the nonstructured one. Therefore as we go on experimenting and construct a sequence of partial models, our confidence in the

148 structure of a "later" partial model may be smaller than in the structure of an earlier one. As we will prove later the mentioned property will hold however, when S' is Cartesian. This is made more precise by the following example. Example 5. 3.1 Consider S = {0,1}3 - {0,1,1}. S is irredundant but not Cartesian. Let X1 and X2 be the following subsets of 5: X1 = {(0,0,0),(1,0,0),(l,l,0)} and X2 = X1 U {(1,1,1),(0,1,0),(1,0,1)}. X, is irredundant, since Pa (X1) = {0} is constant and P{a, }(X1) is irredundant. We will now prove irredundance of X. X2 can be written as the following union: X = {(0,l,0), (l,0,l)} U {(00, 0),(1,,0 ),(,,0 ),(1il,)} = z U z 2 We first note that for every ocED 1 an x CZ s.t. x a (0,1,0). Also for every acD 3 an x gZ2 s.t. x H (1,0,1). Since Z is irredundant (as a minimal independent set), U I holds on Z or all DID2 D with Dl D2 = 0. To prove irredundance of X2, we still have to show that for any x x wD, any D1),D2with D n D2 = {a}, fId< 2U V% 2. This follows easily 1 2 by inspection, since Z2 is irredundant. So X2 is irredundant. We note that S = X2 U {(0,0,1)}. Let S' = S, D' = D and let f be a function from X to S given by 2 2 the table of Figure 5.3.1. We will denote by f the restriction of f 2 to X. Then L(P - f) = }L(P f and L(P f) =. 1 2 1 Thus L1 = {{al},{a2},c} is the reduced structure of f1. One of the structure preserving extensions of fl to S is given by gl of

'I 'SS oaduw1xE jo suo.,ou'a! jo salqej:T''*'S aonmiri (q (O i'o) ( '0'0) (o' 'o I) (I'()o' I'o) (o)0'0) (O'(' 1) (0 '0'o) ('o' T) (0"T~c ) (0'1'1) (0'1'1) (0'(00) ('o"'0) (0' '0) (T0'0..) ( '' I '' ) Z (o'o'T) (oc'TT) ).. (o'"tI) (O O'T) (x)jZ x 6t7

150 Figure 5.3.1. It can be readily verified that the reduced structure of gl is indeed equal to that of f1 and gl:S + S. We find the reduced structure of f2 to be L2 = {{ al},a},{o3}}. There is just one possibility of extending f2 to S., while preserving the structure: namely to map (0,0,1) into (0,1,1). But (0,1,1) is not in S and so there is no structure preserving extension of f2 to S. Thus CONFf(X2)(Lj) > O while CONFf(2)(2) = 0. 0 (S',s ) (L 2S') =. For the remaining part of this section we assume that S' Cartesian. This assumption is a very important one, for we show that in this case we may carry over our results from the nonstructured case. To do so we first prove the following: given any subset X of S and any function f, f:X - S', the number of extensions of f to S with a given structure {LB} is the product of the number of extensions to S of Pelf with location L,3 taken over all t in D'. Proposition 5.3.2 Let S C XSn be irredundant, S' = X S and let f be an arbiaCD aBED' trary function, f:X + S', where X C S. Then for any {LI}BED, s.t. Lg D, v B, and any {ub}$ED, (P. )(x) E(XS) ({L } {ub }) = X E( (L) ub BED' (SS() (L, ub). Proof 1) Let fEE(fX)({L },{ub}). Then clearly PB f is a function from X to P (S') = S'. Also LEL(PB f). f = X PS f and obviously BED' Pi'f is an extension of Pu'f. Clearly I L~EL(PB'f) with ILBI < ub. P?.Y(X) So for v eD', P' feE (s, s) (Lsub), which implies that

151 f ED kS St) (Lub ( rEX BPBEf(S;SS) (L^ P (X) 2) We will now show that for every f~X EP(SS(X) (,ub), 4ED' (S,SSt) (n'ubB)' fEf(X) ({L }, {ub }) f = X f, where fg E(s,) (L3ub). So clearly P 'f = fs and I'(S ) ( u L = L(P'f) holds. fjX = Pf f = (X f) I>X = (f IX) X (Pgs') = f. Also since S' = X S, f:S - S'. So BeD' 8ED' fEEX,) ({L }, {ub }), which completes the proof. With the result of Proposition 5.3.2 in hand we will now show that confidence in a structured case can be expressed as a product of "component" confidences. Corollary 5.3.1 Let S be irredundant, S C XSs and let S' = X S'. Let XC S asD $sDI' and let f:X -* S', where {Lf }ED' is a reduced structure off. Then for any {ub,}~I, -(1) f (X) (1) CONF,){) = (LSub ). ~sD' Proof (See Proposition 5.3.1.) a) Ef(XS) (-,{ub5}) = 0 > f:S + S' s.t. fix = f and for V BSD' 3 an L eL(P' f) with ILsl <- ub,. It follows from Proposition 5.3.2 then, that 3 S~D' s.t. 4 f~~E(S S) (-,ubs). But this imp-'f(X) plies that 3 a SED' s.t. CONF(ss) (Lub) = O. Thus (1) holds in

152 this case. -(X) Pg-~(x ) b) For E( ' {ubj}) L ( E b) For EJ(b S,S') (- ubs) # ( holds and CON~ f(X) ({L },{ub }) | ( )E )(, IM (ss *I ls Pg* fE(X) f (S4,S) (L} ub ) = CONF(s's') (L',ub) 3TIE (S SI) (',ub )I This follows again from Proposition 5.3.2. (Note that {L} D' P') E LI(us,(b ) L <ubf f and Pf) P P$~ ub(, f L0 E (SS') )(L' 3)b) = S P BL' ~ x LBD ' ( ~ L B j ub Remark In case IubI = DI = n for all 3ED', and {L} is a structure of f CONFXs,)(s{L }) )= 1 IS' {( S -L (S 1) )- (I PL (X) I) Theorem 5.3.1 Let S C XS be irredundant and let S' = S. Then the 0:D L SD' following hold. a) Let XC S and let f:X -t S'. Then for any {LB}6SD, s.t. EL(P f), V, if {ub} and {ub} are such that

153 ILE | < ub holds for V CONF, ') ({LSub}) < CONF )({LS}{ub }) b) Let X1,X2 be irredundant subsets of S, where C i X1 X2 holds. Let f2:X2 + S' and let fl = f2jX1. Then with L1 = {L(Ps-) )} and L2 = {L(P3f 2)}B ED' CONFfl(XI)(L UB) < CONFf2(X2)(L,UB) holds for any (S,S') ' (S,S )2 family of integers UB = {ub }BD, s.t. 0 < ubB <n, provided that if IL(P- fl) J -< ub holds then JL(PB.f2) 1 -< ub holds. c) Let X be an irredundant subset of S. Let f:X + S' and let L = {L(P -f)}E~D" Then for any UB = {ubB} CONF(S' S)( Lub) - CONFx,) (LUB). d) Let X be an irredundant subset of S. Let f and g be functions from X to S', where L(P.-f) C L(PP-g) holds for all B3ED'. Let L- and L- denote the reduced structures of f and g respecf g tively. Then CONFf(X) (~ UB) < O (X) CONFf) L- UB) CONF(x) (L-,UB) holds for any (S,S') f' (S,S') g' family UB = {ubB}, provided that if IL(PS.f) -< ubS then L(Psg) I < ubs, holds for V 8CD'. Proof a) Follows directly from Propositions 4.2.2 and 5.3.2. b) Follows directly from Theorem 4.2.1 and Proposition 5.3.2. c) Follows directly from Proposition 4.2.3 by applying Proposition 5.3.2. d) Follows from Propositions 4.2.4 and 5.3.2. a

154 In case of structured functions we define an average confidence for an irredundant subset X of S in an analogous way to that of Chapter 4. Thus for UB = {ub }b3D, ZUB is a random variable, ZUB:F(S S, ) ITR, defined by ZuB(f) = CONF( sX)(STR(fIX),UB), where STR(f|X) denotes the reduced structure of fiX. (This structure is unique, since X is irredundant.) Then ACONF S S)(UB) = E(ZUBJUB) = P(f|UB)-ZUB(f). (Ss') It turns out that average confidence can also be expressed as a product of "component" average confidences. Proposition 5.3.3 Let S 9C >S be irredundant and let X be an irredundant subset of S. Further let S'= X S'. Then for any UB = {ubS}ED, ACONFS, S)(UB) = I ACGONF,S)(ubb)). Proof It follows from the definition that ACONF, S') (UB) = 1 f'X IF (SS((,UB) f F (UB) (S,S') ({(PB fIX)},UB) (S)S') f~F (~,Vf l (S,S') 1 ( Z TCONF(ss) (L(P'.fX) ub})) IF (s,S')(" UbR)I fEF(ss,) (,)UB) TT IF( S's('b)F g ( S'SS) ('UB)) FT I(SS?)(uR)I( F) ubN 'S )(L(f X),ub))) =

155 1 fIX B3CD' P' ( 1 SI)( E CONF (S (L(f IX),ub)))= 13ED (SS)(ubb)! f,F (b VT ACONFXS (). ss))(ub r[[3eD' ( 's,so) s We are now ready to show that results of Propositions 4.2.5 and 4.2.6 carry over to the structured case with obvious modifications. Theorem 5.3.2 Let S C XS. be irredundant and let S' = X S'. Then the acD X3ED' following hold. a) Let X be an irredundant subset of S and let UB = {ub}D, be given. Then ACONF, (i)(UB) (S, S') (S' (fF (x (,UB) (SS)(,UB) where STR(f) is the reduced structure of f. b) Let X1,X2 be irredundant subsets of S, where X1 C 2holds. Then for any UB = {ub }IFD, ACONF (S' S (UB) < ACONF (UB)~ (SS') (SCO(3 Proof a) The proof of this is analogous to the proof of Proposition 4.2.5, when Corollary 5.3.1 is applied. b) Follows directly from Propositions 4.2.6 and 5.3.3. a

156 The bounds for average confidence function can be readily computed on the basis of Propositions 4.2.7 and 5.3.3. The important property of average confidence, which we were able to prove is its monotonicity with increasing data set size. Thus as we enlarge our experimental domain subsets, the trend will be to increase our average confidence. We now turn to the topic of prediction making in structured case. Suppose that we know the actual function f on X, a proper subset of S. We would like to predict as much of f on S-X as possible. We do not want to do it randomly, but use the information we already have about f as a basis for our predictions. We will proceed in the following way. If f is the restriction of f to X and L = {Lo} is a reduced structure of f, we will define a function f from COIMPLSB(X) to S' in the \/i ' wh"L following way: f = X,f where f is the unique extension of Pg f BE:D to n COMPLX(X with location Lo. (See Lemma 3.3.1 and CorolEsD' lary 3.3.3.) Since S' is Cartesian f is well defined. f is our prediction of f to n COMPLLS(X) and it satisfies the following heuristic: BED' 1) Any guess at f ought to agree with the observed portion of (f(fX = f). 2) Any guess at f ought to have a structure so far estimated for f (L 3L(P - L)). 3) We are justified in guessing at point in S just when our guess is uniquely determined by imposing requirements 1) and 2), i.e. when our guess is constrained by so-far-acquired data. We note that Q COMPLS (X) is the largest subset of S with eed'

157 LB property 3. This follows from the fact that COMPLS (X) is the largest subset Zs of S s.t. for every fCE (Ss) (L), f jZB is unique. (See section 4 of Chapter 4.) We will refer t (:()P11'1. (X) _ cD' f(X) f(X) explanatory range of f, denoted by EXPL MS)(L). EXPL(SS) (L)-x is denoted by PREDf(X) (L). PCONF(X) ({L },{ub }) is defined analo(S,S') (SS') B gously as in Chapter 4. We remark that our prediction making approach is quite different from the usual one. The main difference being the concept of predictive range. In usual view of predictions no distinction is possible between points at which prediction is systematically determined by acquired data as opposed to points, at which prediction is not truly constrained by the data. Proposition 5.3.4 Let S C XS and S' = X St. Further let X be a subset of S a ED tD' and let f:X + S', where fcF(x s,)(-UB). Then for any structure {Ls}B ' Of f 'f(fY) (. oB)I a) PCONF(S, ({L}UB) = SS), where Ef(X) (.UB) IE(S,S')(') Y = EXPL(S S)({L}) and f is a unique extension of f to Y with a structure {L.}. b) If ub~ = n, for all (ED' PCONFf(X) ({ }) = IS' I () P OF(S, S') ({B}

158 Proof Identical to that of Proposition 4.3.1. n We thus showed that the greater the predictive range the (exponentially) smaller the probability of being correct. But note that every misprediction on the predictive range is informative —it invalidates the hypothesis that the actual f has structure {Lf}, and so forces us to increase at least one component location (in case X is irredundant). 5.4 Strategies for Experimentation In this section we will apply our results to finite autonomous discrete time systems. Those systems are time invariant systems of the form <S, 6>, where S is a state space of the system and 6 its state transition function (a map on S). A system <S,6> evolves in discrete time, so that for any state s and any time t, 6(s) represents the state of the system at a next time step. Such a system is a special case of a system of section 5.3 (because the domain and codomain sets are same, S = S'). The interpretation of a partial model of <S,6> and structured partial model of <S,6> are clear. We will propose here several strategies, which a modeller might follow during the experimental process. They are divided into nonadaptive and adaptive classes. In non-adaptive strategies the sequence of test sets is fixed and experimentation consists of transition acquisition for the successive sets until a given structural confidence level is achieved. For this purpose we employ Y< (or 4) sets because of

159 their desirable properties, in particular the computational ones. The disadvantage of the Yk sets is their exponential growth, which limits the feasibility of their use to relatively small k. The Yk sets may still be useful however, since models with relatively small interaction are sought in applications. In adaptive strategies, the sequence of test sets is determined on the basis of prior experimentation. Here the problem of generating a minimal irredundant set, which includes a given set arises. Although no fully satisfactory solution has been obtained, we shall assume that given a subset X, it is feasible to generate a "reasonably" small irredundant set containing X (actually an irredundant subset of X would also work in the following strategies). We assume now that any data point can be generated for the system being modelled. This for example can be achieved, when many identical copies of the system are available. This also will be the case, when an expression or a formula for transition function generation is available, but actual generation is done on demand by a computer program. Or simply, when all data has been collected and stored in memory in a form suitable for table look up. The existence of feasible algorithms for location determination is also assumed. Some initial thought has revealed that these algorithms are strongly dependent on the order of coordinate testing. It will be important to investigate the computational aspects of this process before implementation of the suggested strategies is attempted. We assume that the state set of our system is Cartesian. The following strategy is non-adaptive. It employs once-and-for all computation.

160 Strategy 1 We assume the desired structural confidence level C is given. For k = 1,2,...,n-1 we compute a minimum confidence on YY,mk. We then find a minimum k, for which mk > C holds. We note that the {mk} can be computed once-and-for-all, and a change in C will simply result in a different miminum k. All the computations are done prior to any experimentation. If a k as above exists, we generate the Yk data and whatever the reduced structure of our partial model, the confidence in it will be high enough. In another variant, upper bound information on location sizes is assumed given. This further increases feasibility (since mk will be higher for every k) and makes system identification with confidence 1 possible. The following strategy is non-adaptive. It employs a stopping rule based on achieved confidence. Strategy 2 Again we are given a structural confidence level-C to be achieved. We start with YY, find the reduced structure of the partial model and compute the confidence in it. If this is high enough (that is at least as large as C) we stop. At this point we know the system structure with given confidence. If the confidence is not high enough we go to YY and repeat the process. In case YY does not give us high enough confidence we may use n-l any superset of it for structure and confidence computation. This is possible because every superset of Yn is irredundant (see Remark following Corollary 3.4.2). Hopefully the required level of confidence is

161 achieved before the entire state space has been covered. We note that strategy 2 may be applicable even when strategy 1 is not. Of course, if Yk data need to be generated for strategy 2 and k2 2 YY for strategy 1, then Yk C Yk will hold (assuming equal specified C k1 k2- k1 values). A variant of this strategy employs average structural confidence to guide us in an initial choice of k (here we always start with k = 1). Although this might lead to unnecessarily large Yk in our particular case, we may avoid several iteration steps (recomputation of partial models and confidences in their reduced structure). The following strategy will lead to finding the system structure, when an upper bound on its complexity is given (smaller than the cardinality of the index set). Strategy 3 We assume that all locations are smaller than or equal to k in size, where 1 < k - n-l, and we want to find them. Version 1 We generate YY data and find a partial model structure. This is a structure of our model. Also the state transition function of our system can be identified if necessary. Version 2 In this version, rather than generate the entire Yk set we proceed in the following way. Let L1,L,..., L. be some enumeration of (ksubsets of D with cardinality k. We set L = ~, for all c in D. For i = 1,...,(k) we do the following.

162 For every ac in D we compute L(P -i), where 6i is the transition L. cc cx ciXL. a D = D-a and go to the next a in D. If a) D = c or b) i = we are done with {L } the desired model structure. If not we go to the next i and repeat the process. Version 3 We assume an enumeration L1,L2,...,L. as in version 2. Let ZO = A. For i = l,...,(k we do the following. Zi = Z. tU For every acD we compute L = L(P 6.i), where 6.i is a transition function on Z.. 1 If I L i = k, set D = D-a and go to the next a in D. If a) D = or b) i = (k)we are done with {La} the reduced structure of 6. Else we go to the next i and repeat the process. What enables us to find locations in this manner is the fact, that L(iX | U... J 4) )= QL((61 ). (Proposition 3.2.3.) While all the versions of strategy 3 lead to finding the reduced model structure, in the last two versions we might not have to generate the entire YY set. This might for example happen when L(P 06) are all same and have cardinality k. The essential difference between versions 2 and 3 is, that while in the latter we are finding locations on the union of XL. sets, in the former we are taking the unions of corresponding locations. Efficiency of version 3 is strongly dependent on enumeration assumed. In version 2 a number of points to be compared at every step is step independent, which is not true in version 3.

163 Version 2 seems to be more efficient than version 3. The next strategy is adaptive in the sense that we do not proceed in a fixed way with data generation (as was the case till now). Strategy 4 A desired structural confidence level-C is given. We start with an arbitrary subset X1 of S. We construct a Y1 = IR(X1) - a minimal irredundant superset of Xi and generate data for it. We then perform structure and confidence computations on Y1. If the confidence is high enough we are done. If not we pick an arbitrary subset Z1 of points of S (outside of Y1). We set X= Y U Z and repeat the process. At every stage we may use increment sets-Zi with same cardinality, say p, or vary the size at every set generation. In a variant of the above strategy we do not attempt to construct irredundant sets at every stage. In this case however, all possible minimal structures may have to be computed. Moreover if ci denotes a maximal confidence on Xi, we are not assured that ci+1 > ci holds. The following strategy is adaptive and is analogous to the usual cycle of testing and modification often used in scientific modelling. We will employ here our predictive concept. Strategy 5 We start with a small irredundant subset X of S (this could be a minimal set of Proposition 2.3.2). At cycle i, we find the reduced structure, STRi, of 6 on X.. (6 is the transition function observed o1 1 on Xi.)

164 Starting at an arbitrary state in X. we generate a trajectory employing 6 until either a) a predicted state along the trajectory does not match the corresponding experimental state or b) we reach a state in which 6 is undefined (6 is the prediction of our transition function) or which has been previously visited (indicating a cycle has been entered into). In case a), we add the states generated along the trajectory until mismatch, to X. and set the new Xi to a minimal irredundant 1 1+1 set containing Xi and the added data, then we start cycle i + 1. In case b) we select a new point in X. to initiate trajectory generation and start cycle i again. As long as we remain in cycle i the structural confidence is increasing. This follows from Remark following Proposition 4.2.3. If we wish, we can stop when a prespecified confidence level has been 6 (X.) achieved. If we exhaust PRED(s 's (STRi) before attaining this confidence, we set X i+ to a minimal irredundant set properly containing 6(Xi) Xi U PRED(S S) (STRi). We then start cycle i + 1. Now note that the sets X1,X2,... form an increasing nested sequence so structural confidence is nondecreasing in this process. Since the structural confidence cannot stabilize at a "false peak", it must eventually increase to any preset level. Alternatively, we can employ the heuristic rule: stop when the structural confidence computed does not change for a "long enough time". A variant of this strategy does not employ 6 for a trajectory 6(Xi) generation. Rather we pick subsets of PRED (STRi) for comparison (SS)of our prediction of our predictions and experimental values.

165 Notice that in the above strategy we employ our predictive concept to orient experimentation towards tests of the hypothesis: "the actual system has the same influencer set as our partial model". Every misprediction is informative in the sense of requiring an extension of at least one influence set. Finally, suppose that a modeller is interested in determining whether there exists a structured model of the system in j-class, i.e. such that every influencer set is smaller than or equal to j in cardinality (j < n). The necessary and sufficient conditions for excluding such a class on the basis of partial experimentation are not available. This results from the fact, that adding even one data point to a set may considerably enlarge location sizes. We will explain next a strategy for excluding j-class of models (the sufficient conditions for such an exclusion). Strategy 6 We start with an arbitrary irredundant subset X of S. We find a partial reduced model of the system. If this model is not in j-class there is no system model in this class. Otherwise for every a in D do the following. With {L } a reduced structure of a partial model, make L P ~6(X) the prediction 6 of P '. to COMPL S(X) = PRED ( (L )U X. Let L = {LIL C D, ILU = j, and L DL }. For every L in L, we form COMPLs(X). If for every LEL there exists a point of disagreement in COMMPLS(X) between the predictions and experimental data, IL(P.6) I > j and we stop. The model in j-class has been excluded. (This follows directly from Proposition 4.3.2.) If not set D = D-c and go to next O.

166 If D = a and the j-class model has not been excluded yet, we may try the same method on a larger subset of S. (In the process though, our confidence in existence of a model in j-class has increased.) The above strategies do not exhaust all the possibilities. There are many variants of them involving minor modifications. However, we feel they illustrate the spirit, in which the theory developed can be used to aid the experimental process.

CHAPTER VI CONCLUS IONS 6.1 Summary In this study we considered the problem of modelling autonomous discrete time systems with structured state spaces, on the basis of partial data; special emphasis was placed on structure inference and identification. We first developed the theory of coordinatizations of abstract sets. We pointed out the importance of irredundant coordinatizations and their ramifications for modelling enterprise. Ways of irredundant set generation and criteria for irredundance were set forth. We then studied properties of functions with structured domains. In particular the relation between locations of function restrictions to a sequence of nested subsets of a function domain has been explored. Also the construction of extensions with given locations has been studied: a method for their enumeration was given. Ways of constructing special Cartesian domain subsets have been proposed to be used for structure identification. The computational properties of those subsets and their relative sizes have been discussed. A notion of structured partial models has been formalized and several measures of model performance introduced. Structural confidence, predictive range and predictive confidence for a partial model 167

168 were defined and their properties and dependence on parameters analyzed. Furthermore, we showed how to compute the above measures. A methodology for predicting state-transitions not yet observed was proposed, whereby predictions are constrained by so-far-acquired data. Finally, based on the theory developed, a number of strategies for experimentation was proposed. Their advantages and drawbacks were discussed at some length. 6.2 Suggestions for Further Research Several topics for further research emerge from this study. Considerable amount of work remains to be done in the area of algorithms for location determination. It is of interest to investigate their complexity as well as various computational trade-offs between multiple location determination and irredundant set generation. To this end one has to seek an algorithm for a minimal irredundant superset generation. Since the solution of the above will most certainly depend on the type of coordinatization involved, the hierarchy of coordinatizations should be further investigated. More specifically, new sufficient conditions for moving up the hierarchy should be sought. Also more research is needed to elucidate the relationships between properties of a coordinatized set X and corresponding properties of its graph-theoretic representation. Once all of the above is accomplished,the development of an interactive computer package to aid modelling efforts would become feasible. Finally, we suggest that the theory and methodology developed can be extended to I/O, nondeterministic and stochastic systems.

APPENDIX A IRREDUNDANCE OF CERTAIN Rn SUBSETS In general the result of Example 2.2.4 cannot be extended to hold for a convex subset with a nonempty interior. This is illustrated by the following example. Example A.1 Consider S a subset of R2 as in Figure A.l1 a). Then S is clearly convex and Int(S) # p. But S is not irredundant. This follows easily, since for the point p of S as indicated in Figure A.1 a), [p] = [p]S = {p}. Clearly then, IS l S # I. 1 a(X2 We will show however that every subset S of Rn, where n ~ n Sn = {(Pl...'pn) IPi O, V i, ipi ~ 1} is irredundant. Lemma A.1 n Let S = {(Pl, DPn) 1Pi > 0 v i, and ~Pi, pR }a Then Bnd(S n)= {(p,...pn) i s.t. pi = or p= l}. Proof We will identify the Int(S ) and Bnd(S ). n n n n Let F = { (Pl''''', I a i s.t Pi = or We will show that Bnd(Sn) = F. First we show that F CBnd(Sn). We will use here the Euclidean 169

170 metric on IRn, namely d(x,y) = ((xiy)) where i=l x = (xi)n and y = (yi) n icl i=l Let x6F be given. To prove that xEBnd(S n) we need to show that for every ~ > 0, p a pEIn s.t. d(x,p) < s, but pSn. Choose any ~ > 0. Let C be any positive number s.t. o < C. a) 3 an i, s.t. x. = 0, say io. Let p be a point defined by Xi i f i Pi. Then Pi < 0 and so clearly pS n. A. -~ 1=) 2^ Also d(p,_) = (( ). < ~. So xcBnd(S ). n b) i i s.t. x = 0, but x = 1 holds. Pick any 1 < i n. i= lxi i i is Let p be a point defined by Pi = Then + = X + = 1 + > 1. So pLS. But d(p,x) = ~ < ~. So F C Bnd(Sn). To show that Bnd(S ) C F, it suffices to show that every point xESn s.t. x. # 0 for all i and Zx. < 1 is an interior point of S n Let x as above be given. To show xeInt(Sn) we need to show that 3 > 0 s. t. {p ld(p,x) <E:} C Snd Let gi > 0 be such that x. - ei > 0 and xi + ci < 1. For every i, such ei clearly exists. Let ~ > O be such that xi. + nC < 1. Since E ~~i <E1 such an ~ exi=l Zx. < 1, such an E exists. 1

171 Finally, let E = min(minci,,). Then x. - C > 0 and x. + E < 1 n holds for all i and Zxi + nc < 1 holds. With E so chosen we show that i=l {pjd(p,x) <:} C S_. Let p be such that d(p,x) < c. This clearly implies that jxi-PiI < z, v i, i.e. that xi - <<p. < Xi + E and thus that n n Pi > 0, V i. Also pi < Z(xi+e) < 1. So clearly pES. We showed n Let Sn = f(p.P)IP ~0 and fp,. Then S* is an irredundant subset of Rn. Proof We note that Sn is convex and Int(S ) # c is also convex. Thus n n Int(Sn) is irredundant. (This was proved for any open convex set in Iron 1) Induction base n=2. We show that S2 = {(P.P1) )IP1 0 2 ~ 0 and p1 + p2 1} is irredundant. This is clear from Figure A.l.b), since for every point p of S - p', p2 p3} 3 an xInt(S2 ) s.t. pHalx or pH x holds and 21 1 Int(S2) is irredundant. 2) Induction hypothesis We assume that S is irredundant (n ~ 3) and show that this implies irredundance of S. n

172 "2 p 1 2 S2 p2 - 2 3 C.1 x p 1 1 2 2 3 2 p x, p 11 x, p x al C2 g2 A convex set S2 is irredundant b) Figure A.1: Irredundance of Convex Subsets of R2.

173 Let D1,D2 be arbitrary subsets of D s.t. D1 nf D2 D and D1 l DU2 = D. We have to show that fD ~D D2 U I 1CD D1 D2 Let x,yeSn be such that xllD nD Y We want to show, that XlD U DJ Y. a) 3 an i0D1 D2 s.t. x = Yi = 0. Then x,ysSn, S C S, 0 0 where PD-i (S) Sn and P. (Sn) 0. But S is irredundant by induction hypothesis, which in turn implies irredundance of S. So n X1D U 11D y holds. D1 D2 b) M izD1 n D2 s.t. x = = Yi = i.e. x = yi > 0, for V iED, n D2 If i = Yi 1 holds then Yi = x. = 0 for all iCD-D1 nl D2 iD D iFD D1 1 iED1 2 iD1 fD2 and x = y, in which case we are done. So we need to consider only x,y with xllD y such that Xi=. yi < 1 and x. = Yi > 0, V iED JO D 1 2 1 2 iaD ~D2 iED1( D2 For such x and y however, 3 a p,wEInt(Sn) s.t. xllD U H p and wilD U 2 y. This then implies that pDlD D2 w, and so that pHD U ID w. 1 2 We will show that p and w as described exist. For x as above, 3 a set of numbers ci such that n E i 0 for V iED In D2, xi + ci > 0, v i, and Z(xi+ i) < 1. That i=l. 's as above exist can be verified in more detail by the reader. With Xi i~D1 z. + i. iED-D2 Zi and Pi Xi + ~i icD-D1 a i~D2 xilD z and zTD p hold. Further, pzInt(Sn). Similarly we show that a w 1~ ~

174 as above exists. (We note that the case Dl n D2 = c falls into the last category.) So S is irredundant, which completes the proof. n n

REFERENCES [BW1] Burks, A. W., Wright, Y.B. Sequence Generators and Digital Computers. In Proceedings of Symposia in Pure Mathematics. Vol.5, Am. Math. Soc., Providence, Rhode Island, 1962. IF1] Feldman, J. A. Some Decidability Results on Grammatical Inference and Complexity. In Information and Control, 20, 1972. [G1] Gaines, B. R. System Identification, Approximation and Complexity. In Int. J. General Systems. Vol. 3, 1977. [G2] Gnedenko, B. W. Theory of Probability. Chelsea Publishing Company, New York, 1962. [G3] Gold, E. M. Language Identification in the Limit. In Information and Control, 10, 1967. [G4] Graupe, D. Identification of Systems. Van Nostrand Reinhold Company, 1972. [Hi] Hanna, J. F. A New Approach to the Formulation and Testing of Learning Models. Synthese 16, 1966. [HS1] Hartmanis, J., Stearns, R. E. Algebraic Structure Theory of Sequential Machines. Prentice Hall, 1966. [K1] Klir, G. J. On the Representation of Activity Arrays. In Int. J. General Systems. Vol. 2, 1975. [K2]. Identification of Generative Structures in Empirical Data. In Int. J. General Systems. Vol. 3, 1976. 175

176 [M1] Maciejowski, J. M. The iodelling of Systems with Small Observation Sets. Tech. Rep. 138, University of Cambridge, 1976. [R1] Roosen Runge, P. Algebraic Description of Access and Control in Information Processing Systems. Doctoral Dis., The University of Michigan, Ann Arbor, Michigan, 1967. [YA1] Yamada, M., Amoroso, S. Structural and Behavioral Equivalences of Tessellation Automata. In Information and Control 18, 1, 1971. [Z1] Zeigler, B. P. Towards a Formal Theory of Modelling and Simulation: Structure Preserving Morphisms. In J. A.C.M. Vol. 19, 1972. tZ2]. Theory of Modelling and Simulation. Wiley and Sons, New York, 1976. [Z3]. Structuring the Organization of Partial Models. Int. J. General Systems. (In press.) [ZW1] Zeigler, B. P., Weinberg, R. System Theoretic Model Analysis: Computer Simulation of a Living Cell. J. Theoret. Biology 29, 1970.