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!
Just a thought. It might be worthwhile to think of components recursively.
Supposing that identifiers are assigned to simple components and their
leads, then nodes are completely defined as collections of component leads.
Define a component as one of the following:
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