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:
- The algorithm treats unresolved variables as connections between different parts of the tree.
- Using these connections, it identifies independent parts of the pattern, each corresponding to its own system of Diophantine equations.
- 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.
- As a bonus, the backtracking is very simple, and the algorithm can be implemented as a straightforward recursive function.
Top comments (2)
Slovak?
Some comments may only be visible to logged-in visitors. Sign in to view all comments.