Does Chomsky complexity affect genetic programming computational requirements?

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

@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