Consider first the bicyclic monoid, which may be presented as < a,b | ba >. That is, the elements are lists of the symbols a, b, such that you never see a b followed by an a, so elements have the form a^n b^m, and indeed the numbers n,m are sufficient to describe an element of the monoid.
One way to look at it is as parenthesis balancing: replace a,b with (,) respectively and then the monoid is strings of (,) except any matched pairs () are removed.
Now change ( for lots of different elements you might want, say integers for their place in the string maybe. You get a presentation like < p, x \in X | \forall x \in X xp = e >, that is if you see an element of your data set immediately followed by a p (for pop) you can delete both. This is the stack monoid and elements may be described as p^n s, where s is a list of elements of X and may be read as “the stack operations of popping n times and pushing a,” or “the tree traversal of going up n nodes and then going down the path s.”
One way to look at it is as parenthesis balancing: replace a,b with (,) respectively and then the monoid is strings of (,) except any matched pairs () are removed.
Now change ( for lots of different elements you might want, say integers for their place in the string maybe. You get a presentation like < p, x \in X | \forall x \in X xp = e >, that is if you see an element of your data set immediately followed by a p (for pop) you can delete both. This is the stack monoid and elements may be described as p^n s, where s is a list of elements of X and may be read as “the stack operations of popping n times and pushing a,” or “the tree traversal of going up n nodes and then going down the path s.”