title: New computing paradigms suggested by DNA computing: computing by carving.
abstract: Inspired by the experiments in the emerging area of DNA computing, a somewhat unusual type of computation strategy was recently proposed by one of us: to generate a (large) set of candidate solutions of a problem, then remove the non-solutions such that what remains is the set of solutions. This has been called a computation by carving. This idea leads both to a speculation with possible important consequences--computing non-recursively enumerable languages--and to interesting theoretical computer science (formal language) questions.
authors.affiliation: Universitá degli Studi di Pisa, Dipartimento di Informatica Corso Italia 40, Pisa, Italy. mancav@di.unipi.it
authors.forename: V
authors.initials: V
authors.lastname: Manca
authors.forename: C
authors.initials: C
authors.lastname: Martín-Vide
authors.forename: G
authors.initials: G
authors.lastname: Păun
mesh_terms: D000818:Animals; D019295:Computational Biology / Q000379:methods*; D003198:Computer Simulation; D004247:DNA / Q000032:analysis* / Q000235:genetics; D006801:Humans; D008958:Models, Molecular
chemical_list: D004247:DNA