Created by W.Langdon from gp-bibliography.bib Revision:1.3973

@InProceedings{woodward:2005:UKCIb, author = "John R. Woodward", title = "Invariance of Function Complexity under Primitive Recursive Functions", booktitle = "The 5th annual UK Workshop on Computational Intelligence", year = "2005", editor = "Boris Mirkin and George Magoulas", pages = "281--288", address = "London", month = "5-7 " # sep, email = "jrw@cs.bham.ac.uk", keywords = "genetic algorithms, genetic programming, ADF", URL = "http://www.dcs.bbk.ac.uk/ukci05/ukci05proceedings.pdf", size = "8 pages", abstract = "Genetic Programming (GP) \cite{banzhaf:1997:book} often uses a tree form of a graph to represent solutions in a search space. An extension to this representation, Automatically Defined Functions (ADFs) \cite{banzhaf:1997:book} is to allow the ability to express modules. In \cite{woodward:Modularity} we proved that the complexity of a function is independent of the primitive set (function set and terminal set) if the representation has the ability to express modules. This is essentially due to the fact that if a representation can express modules, then it can effectively define its own primitives at a constant cost. This is analogous to the to the result that the complexity of a bit string is independent of the Universal Turing Machine (UTM) (within an additive constant) \cite{ming93introduction}. The constant depending on the UTM but not on the function. The representations typically used in GP are not capable of expressing recursion, however a few researchers have introduced recursion into the representation. These representations are then capable of expressing the primitive recursive functions (PRFs) which are a subclass of the partial recursive function (which correspond to the computable functions). We prove that given two representations which express the PRFs, the complexity of a function with respect to either of these representations is invariant within an additive constant. This is in the same vein as the proof of the invariants of Kolmogorov complexity \cite{ming93introduction} and the proof in \cite{woodward:Modularity}. We comment on the important of the class of PRFs for learning.", notes = "UKCI 2005 http://www.dcs.bbk.ac.uk/ukci05/", }

Genetic Programming entries for John R Woodward