Subtree-Counting Loops

Francois Lemieux, Cristopher Moore, and Denis Therien

To appear in Quasigroups and Related Systems.

An important objective of the algebraic theory of languages is to determine the combinatorial properties of the languages recognized by finite groups and semigroups. In [Therien], 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.

Click here to download


Cris Moore <moore@santafe.edu>