A Caltech Library Service

Implementability Among Predicates

Cook, Matthew and Bruck, Jehoshua (2005) Implementability Among Predicates. California Institute of Technology , Pasadena, CA. (Unpublished)

See Usage Policy.


Use this Persistent URL to link to this item:


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)
Bruck, Jehoshua0000-0001-8474-0812
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).
Group:Parallel and Distributed Systems Group
Record Number:CaltechPARADISE:2005.ETR067
Persistent URL:
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
Deposited By: Imported from CaltechPARADISE
Deposited On:22 Mar 2005
Last Modified:22 Nov 2019 09:58

Repository Staff Only: item control page