文章基本信息

标题：Visibly Counter Languages and Constant Depth Circuits
本地全文：下载
作者：Andreas Krebs ; Klaus-J{\"o}rn Lange ; Michael Ludwig 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2015
卷号：30
页码：594-607
DOI：10.4230/LIPIcs.STACS.2015.594
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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[+].
关键词：visibly counter automata; constant depth circuits; AC0; FO[+]