Planar acyclic computation

This paper considers the following problem: given a specification consisting of a set of variables X, a multiset of functions F on those variables, and a cyclic ordering on X ⌣ F, determine whether or not there exists a planar acyclic circuit which realizes the specification. An algorithm is given which produces such a circuit whenever one exists. In proving that our algorithm meets this requirement we provide some simple mathematical characterizations of those specifications which are realizable.

Authors

• W.F. McColl
• M.S. Paterson
• B.H. Bowditch

Keywords

No keywords are indexed for this paper.