Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR14-177 | 14th December 2014 14:16

Visibly Counter Languages and Constant Depth Circuits

RSS-Feed




TR14-177
Authors: Andreas Krebs, Klaus-Joern Lange, Michael Ludwig
Publication: 16th December 2014 20:31
Downloads: 1059
Keywords: 


Abstract:

We examine visibly counter languages, which are languages recognized by visibly counter automata (a.k.a. input driven counter automata). We are able to effectively characterize the visibly counter languages in AC0, and show that they are contained in FO[+].



ISSN 1433-8092 | Imprint