Nominal Monoids

We investigate different notions of nominal words, that is, words that my contain letters from an alphabet as well as names and name-binders. In a first section we construct them from first principles. In a second section we take the point of view that—as in the classical case—words over an alphabet S form a free monoid over S. We define different notions of nominal monoids and reveal nominal words as elements of free nominal monoids. Applications to computer science will be treated in subsequent work.