Invariance of Function Complexity under Primitive Recursive Functions

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

  author =       "John R. Woodward",
  title =        "Invariance of Function Complexity under Primitive
                 Recursive Functions",
  editor =       "Pierre Collet and Marco Tomassini and Marc Ebner and 
                 Steven Gustafson and Anik\'o Ek\'art",
  booktitle =    "Proceedings of the 9th European Conference on Genetic
  publisher =    "Springer",
  series =       "Lecture Notes in Computer Science",
  volume =       "3905",
  year =         "2006",
  address =      "Budapest, Hungary",
  month =        "10 - 12 " # apr,
  organisation = "EvoNet",
  keywords =     "genetic algorithms, genetic programming",
  ISBN =         "3-540-33143-3",
  pages =        "310--319",
  DOI =          "doi:10.1007/11729976_28",
  bibsource =    "DBLP,",
  abstract =     "Genetic Programming (GP) \cite{banzhaf:1997:book}
                 often uses a tree form of a graph to represent
                 solutions. An extension to this representation,
                 Automatically Defined Functions (ADFs) is to allow the
                 ability to express modules. In Woodward 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 reminiscent
                 of the result that the complexity of a bit string is
                 independent of the choice of Universal Turing Machine
                 (UTM) (within an additive constant), 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 their
                 representations. These representations are then capable
                 of expressing a wider classes of functions, for example
                 the primitive recursive functions (PRFs). We prove that
                 given two representations which express the PRFs (and
                 only 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
                 and the proof in Woodward.",
  notes =        "Part of \cite{collet:2006:GP} EuroGP'2006 held in
                 conjunction with EvoCOP2006 and EvoWorkshops2006",

Genetic Programming entries for John R Woodward