next up previous
Next: Various methods for algebraic Up: Algorithms for algebraic pattern Previous: Algorithms for algebraic pattern

Definitions

We first define algebraic pattern matching, the one which interests us in a computer algebra environment. Then we will define structural pattern matching, a simpler and different type of matching.

Algebraic pattern matching is defined as solving the equation

\begin{displaymath}F(x,y, ... a,b,...) \equiv G(x,y, ... m,n,... )\end{displaymath}

by finding

m = Sm(a,b,...)


n = Sn(a,b,...)

etc. such that substituting m, n, etc. by the above expressions gives an identity in x, y, etc. Or

\begin{displaymath}F(x,y, ... a,b,...) - G(x,y, ... S_m(a,b,...),S_n(a,b,...),... ) \equiv 0\end{displaymath}

x, y, ... are called the main variables,

a, b, ... are called the parameters and

m, n, ... are called the pattern variables.

The problem is often extended to dictionaries of patterns. In this case we are searching among a set of patterns Gi and we would like to find all the ones which match a given F. In such a situation, we expect to do better than just a sequential search over each pattern.

Some examples,

\begin{displaymath}\begin{array}{ccc}
\mbox{expression} & \mbox{pattern} & \mbox...
...{B}{x+b_0} &
B = 1,\; A = -1,\; a_0 = 2,\; b_0 = 1
\end{array} \end{displaymath}

From the above examples, it is easy to see that the power of algebraic pattern matching is quite substantial and will include most of other operations, like working with complex numbers and algebraic extensions, factoring, gcds, etc.

Structural pattern matching, at the other end, attempts to match a particular form to a mathematical expression. It is like a data structure problem, or a typing problem. Often structural pattern matching does not require the definition of main variables. Only the first of the above examples would record a structural match. The following examples illustrate structural matching more precisely


\begin{displaymath}\begin{array}{ccc}
\mbox{pattern} & \mbox{matches} & \mbox{do...
...n\mbox{:float}\times p\mbox{:var} & 1.2a-1 & 12a-1
\end{array} \end{displaymath}

Often the pattern variables are allowed to carry typing information, as it is shown in the last line.

There are many possibilities in between these two extremes. Systems will normally implement more than just purely structural matching, often under a form that allows for the matching of missing arguments making the appropriate zero assignments.

Except for the simplest structural matching, all the matching problems are very difficult and in many cases unsolvable. For this reason, heuristic algorithms are the only hope of solving some classes of subproblems.


next up previous
Next: Various methods for algebraic Up: Algorithms for algebraic pattern Previous: Algorithms for algebraic pattern
Gaston Gonnet
1999-07-04