BibSonomy :: bibtex  ::

tag user group author concept BibTeX key search:all search:brazovayeye
A blue social bookmark and publication sharing system.
tags · relations · groups · popular
help · blog · about
login · register
brazovayeye's BibTeX entry:  

Invariance of Function Complexity under Primitive Recursive Functions

Proceedings of the 9th European Conference on Genetic Programming, 3905: 310--319, 2006.
Authors: John R. Woodward
Editors: Pierre Collet and Marco Tomassini and Marc Ebner and Steven Gustafson and Anik\'o Ek\'art
URL: http://link.springer.de/link/service/series/0558/papers/3905/39050310.pdf
Tags: algorithms, genetic programming
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.
| URL | BibTeX  
@inproceedings{eurogp06:Woodward,
title = {Invariance of Function Complexity under Primitive Recursive Functions},
address = {Budapest, Hungary},
author = {John R. Woodward},
booktitle = {Proceedings of the 9th European Conference on Genetic Programming},
editor = {Pierre Collet and Marco Tomassini and Marc Ebner and Steven Gustafson and Anik\'o Ek\'art},
month = {10 - 12 April},
pages = {310--319},
publisher = {Springer},
series = {Lecture Notes in Computer Science},
url = {http://link.springer.de/link/service/series/0558/papers/3905/39050310.pdf},
volume = {3905},
year = {2006},
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.},
bibsource = {DBLP, http://dblp.uni-trier.de}, organisation = {EvoNet}, isbn = {3-540-33143-3}, notes = {Part of \cite{collet:2006:GP} EuroGP'2006 held in conjunction with EvoCOP2006 and EvoWorkshops2006},
keywords = {algorithms, genetic programming }
}