The \$-calculus process algebra for problem solving: A paradigmatic shift in handling hard computational problems

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

@Article{Eberbach2007200,

• author = "Eugene Eberbach",
• title = "The \$-calculus process algebra for problem solving: A paradigmatic shift in handling hard computational problems",
• journal = "Theoretical Computer Science",
• volume = "383",
• number = "2-3",
• pages = "200--243",
• year = "2007",
• note = "Complexity of Algorithms and Computations",
• ISSN = "0304-3975",
• DOI = "DOI:10.1016/j.tcs.2007.04.012",
• URL = "http://www.sciencedirect.com/science/article/B6V1G-4NGKWGF-7/2/07c09787a0b898de98e171ac414f6ddc",
• keywords = "genetic algorithms, genetic programming, Problem solving, Process algebras, Anytime algorithms, SuperTuring models of computation, Bounded rational agents, $-calculus, Intractability, Undecidability, Completeness, Optimality, Search optimality, Total optimality",
• abstract = "The $-calculus is the extension of the [pi]-calculus, built around the central notion of cost and allowing infinity in its operators. We propose the $-calculus as a more complete model for problem solving to provide a support to handle intractability and undecidability. It goes beyond the Turing Machine model. We define the semantics of the $-calculus using a novel optimization method (the k[Omega]-optimization), which approximates a nonexisting universal search algorithm and allows the simulation of many other search methods. In particular, the notion of total optimality has been used to provide an automatic way to deal with intractability of problem solving by optimizing together the quality of solutions and search costs. The sufficient conditions needed for completeness, optimality and total optimality of problem solving search are defined. A very flexible classification scheme of problem solving methods into easy, hard and solvable in the limit classes has been proposed. In particular, the third class deals with non-recursive solutions of undecidable problems. The approach is illustrated by solutions of some intractable and undecidable problems. We also briefly overview two possible implementations of the $-calculus.",
• notes = "GP one technique in many",

}

Genetic Programming entries for Eugene Eberbach

Citations