License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2015.594
URN: urn:nbn:de:0030-drops-49447
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/4944/
Go to the corresponding LIPIcs Volume Portal

Krebs, Andreas ; Lange, Klaus-Jörn ; Ludwig, Michael

Visibly Counter Languages and Constant Depth Circuits

pdf-format:
44.pdf (0.6 MB)

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 AC^0 and show that they are contained in FO[+].

BibTeX - Entry

@InProceedings{krebs_et_al:LIPIcs:2015:4944,
  author =	{Andreas Krebs and Klaus-J{\"o}rn Lange and Michael Ludwig},
  title =	{{Visibly Counter Languages and Constant Depth Circuits}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{594--607},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Ernst W. Mayr and Nicolas Ollinger},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/4944},
  URN =		{urn:nbn:de:0030-drops-49447},
  doi =		{10.4230/LIPIcs.STACS.2015.594},
  annote =	{Keywords: visibly counter automata, constant depth circuits, AC0, FO[+]}
}

Keywords: visibly counter automata, constant depth circuits, AC0, FO[+]
Collection: 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)
Issue Date: 2015
Date of publication: 26.02.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI