Lemieux F., Moore C., Thérien D.
Subtree-counting loops

An important objective of the algebraic theory of languages is to determine the combinatorial properties of the langua\-ges recognized by finite groups and semigroups. In [Thérien D.: Subword counting and nilpotent groups, 1983], finite nilpotent groups are characterized as those groups that have the ability to count subwords. In this paper, we attempt to generalize this result to finite loops. We introduce the notion of subtree-counting and define subtree-counting loops. We prove a number of algebraic results. In particular, we show that all subtree-counting loops and their multiplication groups are nilpotent. We conclude with several small examples and a number of open questions related to computational complexity.