3
$\begingroup$

The RPN expressions

a b + c *

and

f d e + *

are algebraically equivalent, though the names of the variables are different and the order of evaluation is slightly different. The expressions

a b * c +

a b * c *

though they have the same length and number of variables as the first expression, are not algebraically equivalent, i.e. in general

c (a + b) ≠ c + a * b
c (a + b) ≠ a * b * c

Without substituting values for any of the variables, is there a property that we could compute which is the same for a b + c * and f d e + * but not for a b + c * and a b * c + or a b * c *?

Assume the variables are real numbers, not e.g. matrices, so + and * are commutative, but - and ÷ are not.

This is a simple example of a broader question I am interested in: what are some properties that RPN expressions (i.e. unambiguous expression trees) have that are different for algebraically different expressions but do not change when the names or order of evaluation of the variables change?

This would be useful because it would be a kind of fingerprint for algebraic expressions that would not change merely because of choice of variable names.

I realize that this could be a big topic; references to sections of textbooks or research articles are welcome.

$\endgroup$
  • 1
    $\begingroup$ You can compute a canonical RPN expression by replacing the variables by fixed variables in the order they are encountered. This is invariant to renaming variables. $\endgroup$ – Yuval Filmus Jul 20 '15 at 4:00
  • $\begingroup$ True. Doesn't work for equivalent expressions like c a b + *, though. Maybe I should edit the question. $\endgroup$ – Nathaniel M. Beaver Jul 20 '15 at 4:26
  • $\begingroup$ There, that should be more clear. $\endgroup$ – Nathaniel M. Beaver Jul 20 '15 at 4:40
  • $\begingroup$ Is $(a+b)*(a-b)$ equivalent to $a*a-b*b$? I meant of course the corresponding RPNs. Now that is an algebraic equality. Also, do you imply only valid RPNs are considered? $\endgroup$ – Apass.Jack Oct 26 '18 at 20:41
  • $\begingroup$ @Apass.Jack I'm fine with just dealing with commutativity, not the distributive property. But it there's a good way to handle that, I'd certainly be interested. And yes, valid RPNs are the focus. $\endgroup$ – Nathaniel M. Beaver Oct 30 '18 at 3:01
1
+50
$\begingroup$

You ask for a computable property that can be used as a fingerprint for equivalence (algebraic equivalence in your case). There are two general approaches to this kind of question:

  1. Take a canonical element of the equivalence class (a normal form) as the fingerprint.

  2. Take the equivalence class itself as the fingerprint. Of course this requires classes to be finite. For computability of the equivalence class we also need a computable bound on the size of members of the class. (Plus decidability of equivalence. But that is a general requirement, because fingerprints imply this decidability.)

In this answer I only consider the case where you only have addition, subtraction, and multiplication. None of your examples has division, so I assume that this restriction already is relevant for you. In this case, an algebraic expression essentially (up to syntax) is a multivariate polynomial. For example, the expression $x\cdot(x-z-z)$ yields the polynomial $x^2-2xz$ (more precisely $\sum\{x^2, -2\prod\{x,z\}\}$, to stress that polynomials do not carry information about the order of additions or multiplications. That is, $x^2-2xz$ is the same polynomial as e.g. $-2zx+x^2$). This polynomial is already close to the fingerprint you want: Different polynomials are extensionally different over the real numbers. Which means that they can be shown to be different by subtituting suitable real values. Hence polynomials are normal forms for expressions.

Renaming of variables is not yet covered. (Also observe that normalizing to polynomials may have the effect of losing variables: $x+y-x$ would be normalized to $y$, in which $x$ does not occur any more.) But we can take equivalence classes of polynomials: The degree and number of monomials imply a size bound. Equivalence is decidable just by trying out variable renamings. With canonical variable names $x_1, x_2, x_3, \ldots$, the above polynomial $x^2-2xz$ yields the equivalence class $\{x_1^2-2x_1x_2, x_2^2-2x_1x_2\}$.

While we have achieved computability, we do not yet have efficiency. So, can we do any better? Can we have a normal form for polynomials? If you consider the special case where all monomials are the product of two distinct variables (like $x\cdot y$), the problem of canonizing polynomials becomes graph canonization, whose complexity is unknown.

$\endgroup$
  • $\begingroup$ This is some food for thought, but I think I would get more out of your answer if you showed how it applied to a specific example. If the example in the question is unsuitable, feel free to use a different one. $\endgroup$ – Nathaniel M. Beaver Oct 30 '18 at 2:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.