Search NKS | Online
1 - 10 of 25 for Union
![](/common/images/search/spacer.gif)
The tetrahedron network from page 476 is for example given in this representation by
{1 {2, 3, 4}, 2 {1, 3, 4}, 3 {1, 2, 4}, 4 {1, 2, 3}}
The list of nodes reached by following up to n connections from node i are then given by
NodeLists[g_, i_, n_] := NestList[Union[Flatten[# /. g]] &, {i}, n]
The network distance corresponding to the length of the shortest path between two nodes is given by
Distance[g_, {i_, j_}] := Length[NestWhileList[ Union[Flatten[# /. g]] &, {i}, !
Simple examples in Mathematica include:
First[Prepend[p, q]] === q
Join[Join[p, q], r] === Join[p, Join[q, r]]
Partition[Union[p], 1] === Split[Union[p]]
One can set up axiom systems say by combining definitions of programming languages with predicate logic (as done by John McCarthy for Lisp in 1963).
As reflected in their traditional notations—and emphasized by Venn diagrams— And ( ∧ ), Or ( ∨ ) and Not correspond directly to Intersection ( ⋂ ), Union ( ⋃ ) and Complement . If one starts from the single-element set {1} then applying Union , Intersection and Complement one always gets either {} or {1} . … And the reason for this is that with s = {1, 2} the function Union[Complement[s, a], b] corresponding to a b only ever gets to the 3 elements {{1}, {2}, {1, 2}} .
The rules for the multiway system can then be given for example as
{"AAB" "BB", "BA" "ABB"}
The evolution of the system is given by the functions
MWStep[rule_List, slist_List] := Union[Flatten[ Map[Function[s, Map[MWStep1[#, s] &, rule]], slist]]]
MWStep1[p_String q_String, s_String] := Map[StringReplacePart[s, q, #] &, StringPosition[s, p]]
MWEvolveList[rule_, init_List, t_Integer] := NestList[MWStep[rule, #] &, init, t]
An alternative approach uses lists instead of strings, and in effect works by tracing the internal steps that Mathematica goes through in trying out possible matchings. With the rule from above written as
{{x___, 0, 0, 1, y___} {x, 1, 1, y}, {x___, 1, 0, y___} {x, 0, 1, 1, y}}
MWStep can be rewritten as
MWStep[rule_List, slist_List] := Union[Flatten[Map[ReplaceList[#, rule] &, slist], 1]]
The case shown on page 206 is
{"AB" "", "ABA" "ABBAB", "ABABBB" "AAAAABA"}
starting with {"ABABAB"} .
Non-deterministic Turing machines
Generalizing rules from page 888 by making each right-hand side a list of possible outcomes, the list of configurations that can be reached after t steps is given by
NTMEvolve[rule_, inits_, t_Integer] := Nest[ Union[Flatten[Map[NTMStep[rule, #]&, #], 1]]&, inits, t]
NTMStep[rule_List, {s_, a_, n_}] /; 1 ≤ n ≤ Length[a] := Apply[{#1, ReplacePart[a, #2, n], n + #3}&, Replace[{s, a 〚 n 〛 }, rule], {1}]
General properties [of multiway systems]
The merging of states (as done above by Union ) is crucial to the behavior seen. … Given a list of string specifications, a step in the evolution of the multiway system corresponds to
Select[Union[Flatten[Outer[Plus, diff, list, 1], 1]], Abs[#] # &]
Multiway systems based on numbers
One can consider for example the rule n {n + 1, 2 n} implemented by
NestList[Union[Flatten[{# + 1, 2 #}]] &, {0}, t]
In this case there are Fibonacci[t + 2] distinct numbers obtained at step t .
Junctional calculus
Expressions are equivalent when Union[Level[expr, {-1}]] is the same, and this canonical form can be obtained from the axiom system of page 803 by flattening using (a ∘ b) ∘ c a ∘ (b ∘ c) , sorting using a ∘ b b ∘ a , and removing repeats using (a ∘ a) a .
With this setup, a network consisting of just one node is {{1, 1}} and a 1D array of n nodes can be obtained with
CyclicNet[n_] := RotateRight[ Table[Mod[{i - 1, i + 1}, n] + 1, {i, n}]]
With above connections represented as 1 and the below connections as 2 , the node reached by following a succession s of connections from node i is given by
Follow[list_, i_, s_List] := Fold[list 〚 #1 〛 〚 #2 〛 &, i, s]
The total number of distinct nodes reached by following all possible succession of connections up to length d is given by
NeighborNumbers[list_, i_Integer, d_Integer] := Map[Length, NestList[Union[Flatten[list 〚 # 〛 ]] &, Union[list 〚 i 〛 ], d - 1]]
For each such list the rules for the network system then specify how the connections from node i should be rerouted. … With rules set up in this way, each step in the evolution of a network system is given by
NetEvolveStep[{depth_Integer, rule_List}, list_List] := Block[ {new = {}}, Join[Table[Map[NetEvolveStep1[#, list, i] &, Replace[NeighborNumbers[list, i, depth], rule]], {i, Length[list]}], new]]
NetEvolveStep1[s : {___Integer}, list_, i_] := Follow[list, i, s]
NetEvolveStep1[{s1 : {___Integer}, s2 : {___Integer}}, list_, i_] := Length[list] + Length[ AppendTo[new, {Follow[list, i, s1], Follow[list, i, s2]}]]
The set of nodes that can be reached from node i is given by
ConnectedNodes[list_, i_] := FixedPoint[Union[Flatten[{#, list 〚 # 〛 }]] &, {i}]
and disconnected nodes can be removed using
RenumberNodes[list_, seq_] := Map[Position[seq, #] 〚 1, 1 〛 &, list 〚 seq 〛 , {2}]
The sequence of networks obtained on successive steps by applying the rules and then removing all nodes not connected to node number 1 is given by
NetEvolveList[rule_, init_, t_Integer] := NestList[(RenumberNodes[#, ConnectedNodes[#, 1]] &)[ NetEvolveStep[rule, #]] &, init, t]
Note that the nodes in each network are not necessarily numbered in the order that they appear on successive lines in the pictures in the main text.
With this setup successive steps in the evolution of the system can be obtained from
GMAStep[rules_, {list_, nlist_}] := Module[{a, na}, {a, na} = Transpose[Map[Replace[Take[list, {# - 1, # + 1}], rules]&, nlist]]; {Fold[ReplacePart[#, Last[#2], First[#2]]&, list, Transpose[{nlist, a}]], Union[Flatten[nlist + na]]}]
![](/common/images/search/spacer.gif)