Does Chomsky complexity affect genetic programming computational requirements?

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

@InProceedings{Burger:2011:SAICSIT,
  author =       "Clayton Burger and Mathys C. {Du Plessis}",
  title =        "Does Chomsky complexity affect genetic programming
                 computational requirements?",
  booktitle =    "Proceedings of the South African Institute of Computer
                 Scientists and Information Technologists Conference on
                 Knowledge, Innovation and Leadership in a Diverse,
                 Multidisciplinary Environment",
  year =         "2011",
  pages =        "31--39",
  address =      "Cape Town, South Africa",
  publisher =    "ACM",
  keywords =     "genetic algorithms, genetic programming, theory of
                 computation, Turing machines",
  isbn13 =       "978-1-4503-0878-6",
  DOI =          "doi:10.1145/2072221.2072226",
  size =         "9 page",
  abstract =     "This paper presents an exploration into the
                 relationship between Chomsky problem complexity, as
                 defined by Theory of Computation, and the computational
                 requirements to evolve solutions to these problems.
                 Genetic programming is used to explore these
                 computational requirements by evolving Turing machines
                 that accept the languages posed. Quantifiable results
                 are obtained by applying various metrics to the
                 evolutionary success of these evolved Turing machines.
                 The languages posed are samples out of three language
                 classes from the Chomsky hierarchy, with each class
                 having increasing levels of complexity based on the
                 hierarchy. These languages are evolved on a two-tape
                 Turing machine representation by making use of genetic
                 operators found to be effective in the literature. By
                 exploring the effects of the genetic programming
                 algorithm population sizes and coupled genetic operator
                 rates, it was found that the evolutionary success rates
                 of the classes of Regular and Context-Sensitive
                 problems have no statistical difference in
                 computational requirements, while the Context-Free
                 class was found to be more difficult than the other two
                 Chomsky problem classes through the statistical
                 significance discovered when compared to the other
                 classes.",
  notes =        "SAICSIT '11",
  acmid =        "2072226",
}

Genetic Programming entries for Clayton Burger Mathys C Du Plessis

Citations