| Bytes | Lang | Time | Link |
|---|---|---|---|
| 092 | Retina | 241228T062450Z | Neil |
| 120 | Charcoal | 241228T220906Z | Neil |
| 392 | Python3.10 | 241228T013733Z | Ajax1234 |
| 261 | Python | 241227T114654Z | Albert.L |
Retina, 97 92 bytes
\d+
0$(*)2
{`{(\w+)<(\w+)}
$1$2$^$1
)`{(\w+)>(\w+)}
$^$2$1$2
¶.+
$^
+`(\d)(_+)(\d)\3\2\1
^¶
Try it online! Link is to test suite that mostly converts from the given format to what the program wants, which is expressions separated by newlines, fully parenthesised using {}s instead of ()s and no spaces. Explanation: Port of @Albert.Lang's Python answer.
\d+
0$(*)2
Convert integers to unary, wrapping them in markers. Wrapping Retina's * operator in $() makes its arguments default to $& and _ respectively, or I could have just written them out as 0$&*_2. (My previous answer wanted to repeat 1, but this caused a problem because Retina tokenises numbers as a single token so e.g. 10*10 becomes 10101010101010101010 but 2*_2 becomes __2.)
{(\w+)<(\w+)}
$1$2$^$1
Convert {a<b} into aba⁻¹, where a⁻¹ is just the reverse of a.
{(\w+)>(\w+)}
$^$2$1$2
Convert {a>b} into b⁻¹ab.
{`
)`
Repeat the above until all of the operators have been processed.
¶.+
$^
Invert the second expression.
+`(\d)(_+)(\d)\3\2\1
Cancel out any a⁻¹a or bb⁻¹ patterns.
^¶
Check that everything was eliminated.
Charcoal, 120 bytes
F²«≔υζ≔⟦⟦⁰⟧⟧υF⁻S(≡κ)«≔⊟υι≡⊟υ<⊞υ⁺⁺§υ±¹ι±⮌⊟υ⊞υ⁺⁺±⮌ι⊟υι»¿›κ9⊞⊞Oυκ⟦⁰⟧⊞§υ±¹⁺×⊟§υ±¹χIκ»≔⁺⊟ζ±⮌⊟υυW⌊ΦLυ∧κ⁼§υ⊖κ±§υκ≔Φυ∧⁻λι⁻λ⊖ιυ¬υ
Try it online! Link is to verbose version of code. Takes two space- or newline-separated fully parenthesised inputs without spaces. Explanation: Another port of @Albert.Lang's Python answer.
F²«
Loop through each input.
≔υζ
Save the previous pass, if any.
≔⟦⟦⁰⟧⟧υ
Start parsing with no positive integer so far.
F⁻S(
Loop though the next input but ignoring (s as both operators are binary.
≡κ)«
If the next character is a ), then:
≔⊟υι
Get the operator's RHS b.
≡⊟υ<
If the last operator was a <, then...
⊞υ⁺⁺§υ±¹ι±⮌⊟υ
... pop the LHS a and push aba⁻¹.
⊞υ⁺⁺±⮌ι⊟υι
Otherwise pop the LHS a and push b⁻¹ab.
»¿›κ9⊞⊞Oυκ⟦⁰⟧
Otherwise if the next character is < or > then push it and start parsing another positive integer.
⊞§υ±¹⁺×⊟§υ±¹χIκ
Otherwise continue parsing the current positive integer.
»≔⁺⊟ζ±⮌⊟υυ
Invert the second input and concatenate it to the first input.
W⌊ΦLυ∧κ⁼§υ⊖κ±§υκ
While the result contains two consecutive values which are negations of each other...
≔Φυ∧⁻λι⁻λ⊖ιυ
... cancel (remove) those two values.
¬υ
Check whether all of the values could be cancelled.
Python3.10, 392 bytes
Perfect use case for match-case.
lambda a,b:f(a)in[b,f(b)]
def f(a,p=[]):
match a:
case[b,0,[c,1,B]]if b==B:l=c
case[[b,0,c],1,B]if f(b)==f(B):l=f(c)
case[b,0,[c,0,B]]if b==B:l=[[b,0,c],0,B]
case[b,0,[c,0,d]]if'['!=str(b)[0]:l=[[b,0,c],0,[b,0,d]]
case[[b,1,c],1,d]:l=[[b,1,d],1,[c,1,d]]
case[b,_,B]if b==B:l=b
case _:l=a
return l if'['!=str(l)[0]else(U if(U:=[f(i)for i in l])==l or U in p+[a]else f(U,p+[U]))
Python, 261 bytes
import re
l=lambda a,b:f'{a} {b} {a[::-1]}'
g=lambda b,a:f'{a[::-1]} {b} {a}'
f=lambda P,o=' ':f(P[1:],o[::-1]+eval(re.sub('(\\d+)','"\\1."',P[0]))+' ')if P else o!=(o:=re.sub(r" (\.?)(\d)"+8*r"(\d?)"+r"(?:\. \.| )\9\8\7\6\5\4\3\2\1 "," ",o))and f([],o)or' '==o
Takes positive integers as atoms and a Polish-ish function notation l(a,b) ~ (a<b) ; g(a,b) ~ (a>b) to represent the input trees.
I'm sure the code can be streamlined ...
How?
Wikipedia says one example of this structure is group conjugation (in the free group). So I translate inputs like \$(a < b)\$ to something like \$ab a^{-1}\$. What we gain by this is that expression normalisation is extremely simple: adjacent inverses cancel and that's it.
Products are written as space separated juxtaposition. I'm adding a dot at the end of each integer. That way the inverse in the free group can be represented by string reversal for both single integers and products. And normalisation can be done by finding and eliminating two word palindromes.