Let X be an alphabet whose symbols represent elements of a group or monoid G. If u and v are words on X, then the notation u = v will mean that u and v are equal as words, while the notation u =G v will mean that the words u and v represent the same element of the group. Let ≤ be any partial ordering of words on X. A word u is said to be irreducible (with respect to ≤) if there is no word v ≠ u with u =G v and v ≤ u. A word that is not irreducible is said to be reducible.
A word is minimally reducible or L1-reducible if the word itself is reducible, but none of its subwords are reducible. MAF calls the language of all such words (for a particular monoid and word-ordering) the L1 language and an automaton that accepts this language an L1-acceptor. If u is minimally reducible, v is irreducible and u =G v then the equation u =G v is called a primary equation (with respect to G and ≤).
A word is L2-reducible if the word itself is reducible, but any proper prefix is irreducible. If u is L2-reducible but not minimally reducible, v is irreducible and u =G v then the equation u =G v is called a secondary equation if there is no non-empty word p such that u = px, v = py and x =G y.
The definitions given here are non-constructive since for two words u,v we may have no means of deciding whether or not u =G v.
The word problem (for a finite presentation) is the problem of deciding whether two different words in the alphabet of the presentation actually represent different elements in the object presented. There is no general algorithm for solving this problem for either monoids or groups, and no such algorithm can exist. In the following sections we introduce various types of structure using which MAF will attempt to solve the word problem in particular cases.