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 \(\mathrm {NC}^{1}\)- 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 \(\mathrm {AC}^{0}\). We present characterizations and decidability results for various logics and circuit classes. In particular, our approach yields a way to understand \(\mathrm {TC}^{0}\), where the regular approach fails.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Alur, R., Madhusudan, P.: Visibly pushdown languages. In: Babai, L. (eds.) STOC, pp. 202–211. ACM (2004)
Bárány, V., Löding, C., Serre, O.: Regularity problems for visibly pushdown languages. In: Durand, B., Thomas, W. (eds.) STACS 2006. LNCS, vol. 3884, pp. 420–431. Springer, Heidelberg (2006)
David, A., Barrington, M.: Bounded-Width Polynomial-Size Branching Programs Recognize Exactly Those Languages in NC\(^1\). J. Comput. Syst. Sci. 38(1), 150–164 (1989)
David, A., Thérien, D., Straubing, H., Compton, K.J., Barrington, M.: Regular Languages in NC\(^1\). J. Comput. Syst. Sci. 44(3), 478–499 (1992)
David, A., Thérien, D., Barrington, M.: Finite monoids and the fine structure of NC\(^{\text{1 }}\). J. ACM 35(4), 941–952 (1988)
Furst, M.L., Saxe, J.B., Sipser, M.: Parity, circuits, and the polynomial-time hierarchy. In: FOCS, pp. 260–270 (1981)
Håstad, J.: Almost optimal lower bounds for small depth circuits. In: STOC, pp. 6–20. ACM (1986)
Krebs, A., Lange, K., Ludwig, M.: Visibly Counter Languages and Constant Depth Circuits. In: Mayr, E.W., Ollinger, N. (eds.) 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015), Garching, Germany, vol. 30 of LIPIcs, pp. 594–607. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 4–7 March 2015
McKenzie, P., Thomas, M., Vollmer, H.: Extensional uniformity for boolean circuits. SIAM J. Comput. 39(7), 3186–3206 (2010)
Mehlhorn, K.: Pebbling mountain ranges and its application to DCFL-recognition. In: de Bakker, J., van Leeuwen, J. (eds.) Automata Languages and Programming. LNCS, pp. 422–435. Springer, Berlin Heidelberg (1980)
Smolensky, R.: Algebraic methods in the theory of lower bounds for boolean circuit complexity. In: STOC, pp. 77–82 (1987)
Straubing, H.: Finite Automata, Formal Logic, and Circuit Complexity. Birkhäuser, Boston (1994)
Vollmer, H.: Introduction to Circuit Complexity - A Uniform Approach. Texts in theoretical computer science. Springer, Heidelberg (1999)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hahn, M., Krebs, A., Lange, KJ., Ludwig, M. (2015). Visibly Counter Languages and the Structure of \(\mathrm {NC}^{1}\) . In: Italiano, G., Pighizzini, G., Sannella, D. (eds) Mathematical Foundations of Computer Science 2015. MFCS 2015. Lecture Notes in Computer Science(), vol 9235. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-48054-0_32
Download citation
DOI: https://doi.org/10.1007/978-3-662-48054-0_32
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-48053-3
Online ISBN: 978-3-662-48054-0
eBook Packages: Computer ScienceComputer Science (R0)