DEV Community

TryAlgebra
TryAlgebra

Posted on

Tree pattern matching

I managed to find a very effective decomposition of the pattern tree, which gives several useful properties for pattern matching. I finally finished the paper on this topic: https://zenodo.org/records/22972752

Here are the main highlights:

  1. The algorithm treats unresolved variables as connections between different parts of the tree.
  2. Using these connections, it identifies independent parts of the pattern, each corresponding to its own system of Diophantine equations.
  3. During matching, the tree can be matched against independent parts of the pattern in parallel, since the result of matching one part does not affect the matching process of another.
  4. As a bonus, the backtracking is very simple, and the algorithm can be implemented as a straightforward recursive function.

Top comments (2)

Collapse
 
pepapepa profile image
pepapepa •

Slovak?

Some comments may only be visible to logged-in visitors. Sign in to view all comments.