Institutul de Matematică şi Informatică "Vladimir Andrunachievici"
Universitatea de Stat din MoldovaRO EN
Subtree-counting loops
Authors: Lemieux F., Moore C., Thérien D.
– 0.25 Mb
Abstract
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.
E-mail:
___________________
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
E-mail:
___________________-
Denis Thérien
School of Computer Science,
McGil University,
3480 University Street,
McConnell Engineering Building Room 318,
Montreal (Quebec),
Canada H3A 2A7.
E-mail:
Département d'informatique et de mathématique,
Université du Québec a Chicountimi,
555 boulevard de l'Université,
Chicountimi (Quebec),
Canada G7H 2B1.
E-mail:
___________________
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
E-mail:
___________________-
Denis Thérien
School of Computer Science,
McGil University,
3480 University Street,
McConnell Engineering Building Room 318,
Montreal (Quebec),
Canada H3A 2A7.
E-mail:
Fulltext
– 0.25 Mb
Contents
- On B-algebras and quasigroups
- Non-associative algebraic system in cryptology. Protection against "meet in the middle" attack
- On some old and new problems in n-ary groups
- Transversals in groups. 3.Semidirect product of a transversal operation and subgrouop
- Subtree-counting loops
- On quadratic B-algebras
- Algebras of vector-valued functions
- Representations of positional algebras
- The abstract groups (3, 3 | 3, p), their subgroup structure, and their significance for Paige loops
