# Re: Using the RM for ADTs

Date: Fri, 10 Jul 2009 08:52:36 -0400

Message-ID: <LIG5m.12573$Rb6.6154_at_flpi147.ffdc.sbc.com>

"David BL" <davidbl_at_iinet.net.au> wrote in message
news:f2c89a8c-4551-4ec3-aa6e-720606808d6a_at_b25g2000prb.googlegroups.com...

> On Jul 9, 9:16 pm, "Brian Selzer" <br..._at_selzer-software.com> wrote:

*>>
**>> I wasn't denying that there is symmetry, nor that it poses problems for
**>> identification. What I'm arguing is that despite the symmetry, there are
**>> still 8 nodes and 12 resistors in the cube example, which means that
**>> there
**>> must be a means to distinguish between the nodes and the resistors, for
**>> things that are indistinguishable are the same thing: that is the essence
**>> of
**>> identity. The nodes and components in a circuit template can be thought
**>> of
**>> as verticies and hyperedges in a connected hypergraph. Certainly each
**>> vertex can be distinguished from all other verticies and each hyperedge
**>> can
**>> be distinguished from all other hyperedges in the same hypergraph, can't
**>> they?
**>
**> Ok, I understand what you're saying now.
**>
**> I think it is useful to distinguish two mutually exclusive sets:
**>
**> S1: The set of all circuit values where nodes and components have
**> been uniquely identified. The labels are regarded as part of the
**> circuit value.
**>
**> S2: The set of equivalence classes over S1 according to the
**> equivalence relation defined by isomorphism
**>
**> It turns out that it is difficult to represent elements of S2 other
**> than by using some arbitrary representative taken from S1. That is
**> why abstract identifiers necessarily appear in the model.
**>
**> All nodes and components have unique identity in an element of S1.
**> However this doesn't apply to an element of S2 when there is self
**> symmetry in the sense of a nontrivial automorphism.
**>
**> BTW I find it very interesting that the graph isomorphism problem is
**> NP but has not yet been proven P nor NPC. In fact it is suspected
**> that it is neither!
*

Note that a simple component can have 2 or more leads and that a node may only connect one component. For example, a quad, 2-input OR gate that has 14 leads (Vcc, gnd, 8 inputs and 4 outputs), can be transformed into a single 5 input OR gate by connecting the outputs of two of the OR gates to the inputs of a third OR gate, and connecting the output of the third OR gate to an input of the fourth OR gate. Each of the three connections is a node consisting of two leads of the same component.

Thinking of components recursively may simplify the pattern matching because each component can then be represented as either a function

of 2 or more variables for simple components, or a composition of functions that share variables. For example, suppose that d1(a,b) and d2(c,d) represent simple components (diodes), then d2(c,d) is d2(c,b)by alpha conversion so that or1(a,c,b) can be d1(a,b).d2(c,b), where the node that connects d1 and d2 is represented by the variable b. Received on Fri Jul 10 2009 - 14:52:36 CEST