Visibly Counter Languages and Constant Depth Circuits
Andreas Krebs, Klaus-Jörn Lange, Michael J. Ludwig · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2015
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 AC^0 and show that they are contained in FO[+].