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.3872

  author =       "Eugene Eberbach",
  title =        "The \$-calculus process algebra for problem solving: A
                 paradigmatic shift in handling hard computational
  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 =          "",
  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
  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
  notes =        "GP one technique in many",

Genetic Programming entries for Eugene Eberbach