g | x | w | all
Bytes Lang Time Link
092Retina241228T062450ZNeil
120Charcoal241228T220906ZNeil
392Python3.10241228T013733ZAjax1234
261Python241227T114654ZAlbert.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]))

Attempt This Online!

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

Attempt This Online!

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.