Visibly Counter Languages and the Structure of NC1 (bibtex)
by Michael Hahn, Andreas Krebs, Klaus-Jörn Lange, Michael Ludwig
Abstract:
We extend the familiar program of understanding circuit complexity in terms of regular languages to visibly counter languages. Like the regular languages, the visibly counter languages are NC1- complete. We investigate what the visibly counter languages in certain constant depth circuit complexity classes are. We have initiated this in a previous work for AC0. We present characterizations and decidability results for various logics and circuit classes. In particular, our approach yields a way to understand TC0, where the regular approach fails.
Reference:
Visibly Counter Languages and the Structure of NC1 (Michael Hahn, Andreas Krebs, Klaus-Jörn Lange, Michael Ludwig), In Proceedings of Mathematical Foundations of Computer Science (MFCS) 2015, 2015.
Bibtex Entry:
@InProceedings{hahn_visibly_2015,
  author = {Hahn, Michael and Krebs, Andreas and Lange, Klaus-J{\"o}rn and
  Ludwig, Michael},
  title = {Visibly {Counter} {Languages} and the {Structure} of {NC}1},
  booktitle = {Proceedings of {Mathematical} {Foundations} of {Computer}
  {Science} ({MFCS}) 2015},
  year = {2015},
  URL = {https://doi.org/10.1007/978-3-662-48054-0_32},
  abstract = {We extend the familiar program of understanding circuit complexity in terms of regular languages to visibly counter languages. Like the regular languages, the visibly counter languages are NC1- complete. We investigate what the visibly counter languages in certain constant depth circuit complexity classes are. We have initiated this in a previous work for AC0. We present characterizations and decidability results for various logics and circuit classes. In particular, our approach yields a way to understand TC0, where the regular approach fails.}
}
Powered by bibtexbrowser