Volume 6
Summer 2014
Number 1

Generating sets and Decompositions for

idempotent tree languages


Mark Thom and Shelly Wismath

Abstract: A tree language of a given type is any set of terms of that type. We consider here a binary operation + on the set of all arity n terms of the type, which produces a semigroup on the set. Using the characterization by Denecke, Sarasit and Wismath of languages which are idempotent with respect to this binary operation, we give a number of examples of idempotent languages, define generating sets for idempotent languages, and show how any idempotent language may be decomposed into a union of disjoint subsets. This decomposition allows us to assign to every term in an idempotent language a natural number called its idempotency level.