Magmas from cuts

Stream: Equational

[Jose Brox]

Since we are talking about ways to analyze a given equation, I'd like to share an unpolished idea I had to construct infinite magmas and try to solve Astérix/Obélix (then it was solved). I don't know if it has any merit, perhaps it is equivalent to other already existing methods, or perhaps someone with more tools to automate computations can actually apply it with ease:

The idea is vaguely inspired by surreal numbers or Dedekind cuts: our set M is composed by cuts, which are pairs of sets, or pairs of pairs, or something similar, written in notation (a|b) (with a,b again in M). Then we try to write a product satisfying an specific equation, by guessing and imposing relations involving the left and right cuts, until we find a (finite or recursive) completion (this is if our "forcing" is not too restrictive, for which one can look at anti-implications, etc.).

For example, for the Astérix equation x = y(x(yx)) one would start with the following rules, valid only when "everything is disjoint enough":
yx = (x|y)
x(x|y) = (x|y)
y(x|y) = x
Then one would, if lucky, iteratively resolve the ambiguities.

Does anyone have any thoughts on this?

[Terence Tao]

My initial reaction is that it is quite challenging to enforce all of these rules for all values of x and y without creating contradictions between the rules. There were some early attempts to create models of Asterix in this fashion which obeyed that law in some ranges of variables, but not all.

[Michael Bucko]

Thinking of an algorithm.
Could this type of work be done by multiple workers doing different cuts and communicating about the results until the task is solved? Could that communication in any way help the workers with additional information avoid contradictions better?

[Jose Brox]

Michael Bucko ha dicho:

Thinking of an algorithm.
Could this type of work be done by multiple workers doing different cuts and communicating about the results until the task is solved? Could that communication in any way help the workers with additional information avoid contradictions better?

Thank you for thinking about this!
I'm not that sure about parallelization: you need to do saturation as in other cases. E.g., Astérix would be solved by the above, except that at the start, we may have x=(a|y) and then instead of yx=(x|y) we would have yx=a by the third rule, so we have to follow that case and see what happens, then impose any relation that is not yet fixed and is not incompatible with the previous ones... So it is a very sequential process in my opinion, in which in addition you may get infinite metarules of the form x(x|y|y...|y)=x and the such.

[Michael Bucko]

Assuming the process seems to be strongly sequential, I have a couple of questions:

• can we potentially speculatively parallelize (ie. aggressively predict certain outcomes and continue the work given certain assumptions across multiple workers)?
• is there any overlap in the work between across different steps?
• can this problem be perhaps seen from the dependency graph perspective? (different paths, shortest paths etc.)
• can any information be broadcasted across steps? (some rules)