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-005 | 27th October 2000 00:00

The Computing Power of Programs over Finite Monoids

RSS-Feed




TR01-005
Authors: Pascal Tesson, Denis Thérien
Publication: 9th January 2001 16:57
Downloads: 3525
Keywords: 


Abstract:

The formalism of programs over monoids has been studied for its close
connection to parallel complexity classes defined by small-depth
boolean circuits. We investigate two basic questions about this
model. When is a monoid rich enough that it can recognize arbitrary
languages (provided no restriction on length is imposed)? When is a
monoid weak enough that all its computations can be realized in
polynomial length? Surprisingly, these two properties appear to be
dual to each other.



ISSN 1433-8092 | Imprint