CaltechAUTHORS
  A Caltech Library Service

Implementability Among Predicates

Cook, Matthew and Bruck, Jehoshua (2005) Implementability Among Predicates. California Institute of Technology , Pasadena, CA. (Unpublished) http://resolver.caltech.edu/CaltechPARADISE:2005.ETR067

[img]
Preview
PDF
See Usage Policy.

280Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechPARADISE:2005.ETR067

Abstract

Much work has been done to understand when given predicates (relations) on discrete variables can be conjoined to implement other predicates. Indeed, the lattice of "co-clones" (sets of predicates closed under conjunction, variable renaming, and existential quantification of variables) has been investigated steadily from the 1960's to the present. Here, we investigate a more general model, where duplicatability of values is not taken for granted. This model is motivated in part by large scale neural models, where duplicating a value is similar in cost to computing a function, and by quantum mechanics, where values cannot be duplicated. Implementations in this case are naturally given by a graph fragment in which vertices are predicates, internal edges are existentially quantified variables, and "dangling edges" (edges emanating from a vertex but not yet connected to another vertex) are the free variables of the implemented predicate. We examine questions of implementability among predicates in this scenario, and we present the solution to all implementability problems for single predicates on up to three boolean values. However, we find that a variety of proof methods are required, and the question of implementability indeed becomes undecidable for larger predicates, although this is tricky to prove. We find that most predicates cannot implement the 3-way equality predicate, which reaffirms the view that duplicatability of values should not be assumed a priori.


Item Type:Report or Paper (Technical Report)
Additional Information:We would like to thank Erik Winfree for helpful discussions. This research was supported in part by the "Alpha Project" that is funded by a grant from the National Human Genome Research Institute (Grant No. P50 HG02370). http://www.paradise.caltech.edu/papers/etr067.pdf
Group:Parallel and Distributed Systems Group
Record Number:CaltechPARADISE:2005.ETR067
Persistent URL:http://resolver.caltech.edu/CaltechPARADISE:2005.ETR067
Usage Policy:You are granted permission for individual, educational, research and non-commercial reproduction, distribution, display and performance of this work in any format.
ID Code:26094
Collection:CaltechPARADISE
Deposited By: Imported from CaltechPARADISE
Deposited On:22 Mar 2005
Last Modified:26 Dec 2012 13:53

Repository Staff Only: item control page