Group Abstract Group Abstract

Message Boards Message Boards

Question about a quoted expression: {x,y} matches {x,x} ?

Posted 5 years ago
POSTED BY: David Stephenson
9 Replies

I must disagree with your first point. When you subdivide an hypergraph into a set of 2-node edges, there is indeed loss of information.

Consider the hypergraph {{1,2,3}{3,4,5}} in the first picture. (Taken form here) hypergraph

It can be subdivided into the following set:

  • {1,2}
  • {2,3}
  • {3,4}
  • {4,5}

Consider instead the hypergraph {{1,2}{2,3}{3,4}{4,5}} in the second picture.

normal graph

Its decomposition is the same, but the two hypergraphs are not isomorphic, hence there was loss of information during the decomposition process. Also from a pattern matching perspective, it is impossible to determine if a pattern matches an hypergraph, when given only its decomposition. For example, the pattern {{x,y,z}{z,u,v}} matches the first graph but not the second one, while {{x,y}{y,z}{z,u}{u,v}} matches the second one but not the first.

Regarding you second point, I am not aware of any reason against your proposal, but I am not an expert of graph theory, nor I have knowledge of Wolfram's motives when he formulated the theory.

All I can say is that your idea seems good to me. I hope that someone with better knowledge on the subject will comment on that.

POSTED BY: Ruggero Valli

Good to hear your thoughts on the matter.

Allow me to start with your first point, which you eloquently phrased as:

"{x,y,x} is already an edge and subdividing it in {x,y} and {y,x} is meaningless".

On the contrary, since any hypergraph of any size can be accurately defined as an unordered set of its irreducible edges, without any loss of information, it is, in fact, your "already an edge" that is epiphenomenal to the fundamental definition of a hypergraph, not the other way around. The independent variable in the hypergraph is the set of irreducible edges that it is composed of, and the dependent variable is the length of any one particular edge in the hypergraph (an "n-nodes edge"), which will inevitably be composed of one or more irreducible edges.

I am, of course, speaking from a purely informational perspective.

From that perspective, and from the perspective of processing hypergraph information efficiently to both "grow" and store them according to one or more rule sets, there is simply no need whatsoever to deal with an "n-nodes edge". It isn't required for hypergraph storage, pattern matching, or substitution.

Perhaps an example is in order here. Where is the loss of information between defining a hypergraph as:

{{u,u,v},{v,u,y},{z,y,v}}

and defining that same hypergraph as the following set of irreducible edges:

  • {u,u}
  • {u,v}
  • {v,u}
  • {u,y}
  • {z,y}
  • {y,v}

There is, of course, no loss of information. Not only that, but the set is unordered by definition, which is highly fortuitous for pattern matching and substitution purposes (as I'm sure you can imagine).

So no, my friend, "subdividing it in {x,y} and {y,x}" is far from meaningless. Let's put that to bed right now.

Which brings us to your second point, which I (of course) agree with:

"Subdividing a pattern in(to) smaller elements and matching these individually doesn't guarantee that the whole pattern matches. This is essentially the point of using a repeated letter when writing a rule."

Perhaps not as eloquently phrased as your first point, but I know what you mean. To paraphrase: all symbolically equivalent letters in the LHS must match one, and only one, node in the target hypergraph.

I also agree with you that {x,y,x} should not match {u,v,w} for the very reasons you cited.

So okay, there is not, as I previously postulated, a "fundamental contradiction in the syntax". I have to admit that. You've convinced me. But I still find this "many to one" relationship between the nodes in the LHS and the target hypergraph completely arbitrary, unnecessary, counterproductive, and quite frankly, repugnant.

I mean, seriously, if the pattern hypergraph has twenty-three nodes, all intricately laid out, how can you justify it being "matched" by a hypergraph of only one node? Where, in the whole body of graph theory or substitution systems theory, is that justifiable?

And even if it were justifiable in some arcane graph theory tome somewhere, does that make it necessary to the study of the Wolfram Model? I don't believe so.

It would seem to me, therefore, that a much easier, more workable, more algebraically consistent, and empirically more flexible syntax would be defined by the single rule:

A match is found when all the nodes and irreducible edges of a "search" hypergraph is found to exist as a sub-hypergraph in the target.

Simple. Elegant.

Such a syntax would be exactly like the current Wolfram Model syntax, but for the important omission of the "{x,y} will match {x,x}" aberration.

More to say on the subject, but must eat. Interesting dialectic thus far. Kudos.

POSTED BY: David Stephenson

Ok, I think I understand your issue, hopefully.

Firstly, we are talking about hypergraphs not regular graphs. In regular graphs, an edge is a connection between two nodes, for example {u,v} means that node u is connected by an edge to node v. With hypergraphs instead, an edge is a connection between any number of nodes. For example {u,v,w} is a connection between the three nodes u,v and w.

In the same way you can picture a 2-nodes edge as a line connecting the two nodes, you can imagine that a 3-nodes edge is some kind of surface on which the three nodes lay. And a 4-nodes edge like {u,v,w,z} is a 3-dimensional hypersurface, etc. [Technical introduction]

I am sorry for this lengthy and perhaps unnecessary explanation, but I felt like there was some confusion, when you wrote "the {x,y} edge in the {x,y,x} pattern", because {x,y,x} is already an edge and subdividing it in {x, y} and {y, x} is meaningless.

The second remark I would like to make is that even if you had two different edges, for example {{x,y}{y,x}} in the LHS of a rule, it still wouldn't match the pattern {{u,v}{v,w}}. The reason is that patterns must be matched as a whole. Subdividing a pattern in smaller elements and matching these individually doesn't guarantee that the whole pattern matches. This is essentially the point of using a repeated letter when writing a rule.

Consider the rule {{x,y,z}{x,x}} -> {{u,v,x}{x}}.

  • Every time the letter x appears, it must represents the same node.
  • x,y and z could all be labelling the same node.
  • u and v appear only on the RHS, so they must be new nodes, different from any other and also $u \neq v$.

I suggest you look at the first two parts of the technical introduction. The things that we are discussing here are not always stated explicitly, but there are many examples from witch they can be inferred.

POSTED BY: Ruggero Valli

Yes, understanding is "tough" (haughty muffled chortle).. ;)

Because, according to rule 1:

  • the {x,y} edge in the {x,y,x} pattern matches the {u,v} in the target, and
  • the {y,x} edge in the {x,y,x} pattern matches the {v,w} in the target.

Thus, the two edges of the pattern hypergraph (and there are only two) have been matched.

Thus, according to rule 1: {x,y,x} should match {u,v,w}.

POSTED BY: David Stephenson

I think that {x,y,x} does not match {u,v,w}, because of the first reason you mentioned.

If it does, then it breaks rule 2 (because u ≠ w)

I don't understand your second point, tough.

if it doesn't, then it breaks rule 1 ( {x,y}->{u,v}, {y,x}->{v,w} ).

could you clarify how rule 1 contradicts the statement "{x,y,x} does not match {u,v,w}"?

POSTED BY: Ruggero Valli

Actually, I wasn't trying to "make" anything in my last post, I simply asked a single question, to which you gave a wonderfully complete answer. So thank you for that. What fun.

So the pattern-matching rules for the LHS of a Wolfram-compatible rule, as we have previously discussed and agreed upon, are:

  1. {x,y} will match both a {u,u} and a {u,v}.
  2. {x,x} will only match a {u,u}.

So where does that leave the LHS interpretation of something like:

{x,y,x} ?

Specifically, will the above match {u,v,w} ?

  • If it does, then it breaks rule 2 (because uw), and
  • if it doesn't, then it breaks rule 1 ( {x,y}->{u,v}, {y,x}->{v,w} ).

A fundamental contradiction in the syntax.

Apparently.

POSTED BY: David Stephenson
POSTED BY: Ruggero Valli

Thanks for the reply. I was beginning to think I was a ghost.

So will an {x,x} in the LHS of a Wolfram-compatible rule match a {u,v} in the target hypergraph, assuming that u is distinct from v?

BTW, your rule "3" requires amendment. To wit:

"If a new label appears on the left hand side" s/b "If a new label appears on the right hand side".

I have been called a grammar Nazi. Recently. Guilty as charged.

POSTED BY: David Stephenson

Hello, sorry for the late reply, I hope it could still be of use.

I think that the problem with your reasoning stands on the assumption that the initial conditions used for the rule {{x,x,y},{x,z,u}}->{{u,u,v},{v,u,y},{z,y,v}} are exactly {{x,x,y},{x,z,u}}, with $x \neq y \neq z \neq u$, because this is not the simplest initial condition for that rule. I think (please correct me if I'm wrong on this) that the examples of rule evolution found on the catalogue always start from the simplest initial condition to which a rule is applicable.

To clarify my point, let me talk about the first rule shown on the page you linked (Recognizable Geometry), namely {{x, y}} -> {{y, z}, {z, x}}.

I copy here the first steps of evolution reported on the page. enter image description here

As you can see, the initial condition is one single node connected to itself. The single node is doing the double job of being both x and y at the same time. Obviously, this initial condition is the simplest to possible state to which the rule is applicable. So, in the first step there is only node 1 (labelled both x and y) connected to itself. The initial state can therefore be written as {{1,1}}.

You can apply the rule and see that in the right hand side there is a new node, z, which is different from node 1, let's call it node 2. Now {y,z} means there is an edge between node 1 and node 2, and {z,x} means there is an edge between node 2 and node 1. Hence the second step, as shown in the picture, can be written {{1,2}{2,1}}

Let's get now to the rule you asked of: {{x,x,y},{x,z,u}}->{{u,u,v},{v,u,y},{z,y,v}}.

You can see that the simplest initial condition is the one in which x,y,z and u are different labels for the very same node (let's call it node 1). The starting point will be the hypergraph {{1,1,1},{1,1,1}}. One node with two triple connections from the node to itself.

In the right hand side there is the new letter v, therefore a new node must appear, let's call it node 2. After applying the rule you get {{u,u,v},{v,u,y},{z,y,v}}, but $x=y=z=u=1$, so the second step looks like {{1,1,2}, {2,1,1}, {1,1,2}}.

Now you see that you can apply the rule again. Just stick the labels x and z to node 1 and y and u to node 2. With this substitution you can write the second step as, for example, {{x,x,y}, {y,x,x}, {x,z,u}}, to which you can apply the rule and go on with the computation.

To summarize, the way to apply the rules, as I understand it, is:

  1. The left hand side of a rule can be matched even if more than one label is attached to the same node.
  2. Initial conditions are chosen to be as simple as possible (e.g. one node connecting to itself is ok).
  3. If a new label appears on the right hand side, it must correspond to a new node.

I hope this helps

POSTED BY: Ruggero Valli
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard