Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR01-040 | 16th May 2001 00:00

On the Languages Recognized by Nilpotent Groups (a translation of "Sur les Langages Reconnus par des Groupes Nilpotents")

RSS-Feed




TR01-040
Authors: Pierre Péladeau, Denis Thérien
Publication: 23rd May 2001 22:59
Downloads: 3420
Keywords: 


Abstract:

We study a model of computation where executing a program on an input corresponds to calculating a product in a finite monoid. We show that in this model, the subsets of {0,1}^n that can be recognized by nilpotent groups have exponential cardinality.

Translator's note: This is a translation of the article ``Sur les langages reconnus par des groupes nilpotents,'' C. R. Acad. Sci. Paris, t. 306, Serie I, p. 93-95, 1988. It was translated in 1998 with permission from the authors by Alexander and Sarah Russell.



ISSN 1433-8092 | Imprint