Wlodzislaw, We have not addressed formally the algorithmic complexity issue, because the "new" (i.e.based on the last verstion of the ETS model) algorithms for the computation of typicality and for learning a subclass from a training set are not fully developed yet. Preliminary considerations about the complexity are the following:
1. The Induction Axiom (Def. 19 in "What Is a Structural Representation?") guarantees that the directed graph of transformation paths in a class is always acyclic; thus, the typicality is at least computable, if we can algorithmically apply transformations. 2. The complexity of the typicality computation significantly depends on the chosen inductive structure (Def. 20); the more semantic identities (Def. 6) we have, the more paths exist to a given class element, and the more "complex" are both the transformation application procedure and the typicality computation. However, a subclass of a given class can usually be described in another inductive structure, which has less semantic identities and thus allows for a more efficient typicality computation. In this way, even if the computation of the typicality of certain elements "takes too long" in the large class, it can be speeded up by choosing the subclass containing these elements, i.e. by learning a new subclass. 3. The search for a subclass that best fits the training set is defined as a search for an element in the power class (Section 4), and thus, in principle, is not much different from the search for an element in the class or the computation of an element's typicality. However, a formal definition of the power class is needed to completely clarify this analogy. We believe that there is a tight connection between the descriptions (transformation systems, Def. 3) of the class and its corresponding power class; we are currently working on this definition. When developed, it will also clarify what the learning complexity is, since the latter depends on the power class description. Oleg Golubitsky PhD Student, Faculty of Computer Science, University of New Brunswick WD> ETS has some advantages here but there are two problems that need to WD> be addressed. WD> First is the need for efficient implementation of the minimal WD> transformation cost calculations and the second is an efficient WD> implementation of the search for the best substitutes that should WD> allow to discover class structures. WD> We have once worked on algorithmic complexity (or Levin's complexity) WD> that in principle could discover the simplest program solving a given WD> task but in practice it couldn't do much being NP hard. Is there any WD> progress in this direction?
