Title: Non-linear Associative-Commutative Many-to-One Pattern Matching with Sequence Variables,
Abstract: Pattern matching is a powerful tool which is part of many functional
programming languages as well as computer algebra systems such as Mathematica.
Among the existing systems, Mathematica offers the most expressive pattern
matching. Unfortunately, no open source alternative has comparable pattern
matching capabilities. Notably, these features include support for associative
and/or commutative function symbols and sequence variables. While those
features have individually been subject of previous research, their
comprehensive combination has not yet been investigated. Furthermore, in many
applications, a fixed set of patterns is matched repeatedly against different
subjects. This many-to-one matching can be sped up by exploiting similarities
between patterns. Discrimination nets are the state-of-the-art solution for
many-to-one matching. In this thesis, a generalized discrimination net which
supports the full feature set is presented. All algorithms have been
implemented as an open-source library for Python. In experiments on real world
examples, significant speedups of many-to-one over one-to-one matching have
been observed.