IMI/Publicaţii/QRS/Ediţii/QRS v.8, n.1 (8), 2001/

Subtree-counting loops

Authors: Lemieux F., Moore C., Thérien D.


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 [20], 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.

François Lemieux
Département d'informatique et de mathématique,
Université du Québec a Chicountimi,
555 boulevard de l'Université,
Chicountimi (Quebec),
Canada G7H 2B1.
Cristopher Moore
Computer Science Departament,
University of New Mexico,
Farris Engineering Center,
Room 157,
Albuquerque (NM),
USA 87131 and the Santa Fe Institute,
1399 Hyde Park
Road, Santa Fe (NM) USA 87501
Denis Thérien
School of Computer Science,
McGil University,
3480 University Street,
McConnell Engineering Building Room 318,
Montreal (Quebec),
Canada H3A 2A7.


Adobe PDF document0.25 Mb