Document Open Access Logo

Visibly Counter Languages and Constant Depth Circuits

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

PDF
Thumbnail PDF

File

LIPIcs.STACS.2015.594.pdf
  • Filesize: 0.62 MB
  • 14 pages

Document Identifiers

Author Details

Andreas Krebs
Klaus-Jörn Lange
Michael Ludwig

Cite As Get BibTex

Andreas Krebs, Klaus-Jörn Lange, and Michael Ludwig. Visibly Counter Languages and Constant Depth Circuits. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 594-607, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.STACS.2015.594

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[+].

Subject Classification

Keywords
  • visibly counter automata
  • constant depth circuits
  • AC0
  • FO[+]

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Rajeev Alur and P. Madhusudan. Visibly pushdown languages. In László Babai, editor, STOC, pages 202-211. ACM, 2004. Google Scholar
  2. Vince Bárány, Christof Löding, and Olivier Serre. Regularity problems for visibly pushdown languages. In Bruno Durand and Wolfgang Thomas, editors, STACS 2006, 23rd Annual Symposium on Theoretical Aspects of Computer Science, Marseille, France, February 23-25, 2006, Proceedings, volume 3884 of Lecture Notes in Computer Science, pages 420-431. Springer, 2006. Google Scholar
  3. David A. Mix Barrington. Bounded-width polynomial-size branching programs recognize exactly those languages in NC¹. J. Comput. Syst. Sci., 38(1):150-164, 1989. Google Scholar
  4. David A. Mix Barrington, Kevin J. Compton, Howard Straubing, and Denis Thérien. Regular languages in NC¹. J. Comput. Syst. Sci., 44(3):478-499, 1992. Google Scholar
  5. David A. Mix Barrington and Denis Thérien. Finite monoids and the fine structure of NC¹. J. ACM, 35(4):941-952, 1988. Google Scholar
  6. Mikolaj Bojańczyk and Igor Walukiewicz. Forest algebras, 2007. Google Scholar
  7. Ashok K. Chandra, Steven Fortune, and Richard J. Lipton. Unbounded fan-in circuits and associative functions. J. Comput. Syst. Sci., 30(2):222-234, 1985. Google Scholar
  8. Patrick W. Dymond. Input-driven languages are in log n depth. Inf. Process. Lett., 26(5):247-250, 1988. Google Scholar
  9. Merrick L. Furst, James B. Saxe, and Michael Sipser. Parity, circuits, and the polynomial-time hierarchy. In FOCS, pages 260-270, 1981. Google Scholar
  10. Yuri Gurevich and Harry R. Lewis. A logic for constant-depth circuits. Information and Control, 61(1):65-74, 1984. Google Scholar
  11. Johan Håstad. Almost optimal lower bounds for small depth circuits. In STOC, pages 6-20. ACM, 1986. Google Scholar
  12. Neil Immerman. Languages that capture complexity classes. SIAM J. Comput., 16(4):760-778, 1987. Google Scholar
  13. Neil Immerman. Descriptive Complexity. Springer, New York, 1999. Google Scholar
  14. Andreas Krebs and Klaus-Jörn Lange. Dense completeness. In Hsu-Chun Yen and Oscar H. Ibarra, editors, Developments in Language Theory - 16th International Conference, DLT 2012, Taipei, Taiwan, August 14-17, 2012. Proceedings, volume 7410 of Lecture Notes in Computer Science, pages 178-189. Springer, 2012. Google Scholar
  15. Pierre McKenzie, Michael Thomas, and Heribert Vollmer. Extensional uniformity for boolean circuits. SIAM J. Comput., 39(7):3186-3206, 2010. Google Scholar
  16. Robert McNaughton and Seymour Papert. Counter-free automata. With an appendix by William Henneman., 1971. Google Scholar
  17. Kurt Mehlhorn. Pebbling mountain ranges and its application to dcfl-recognition. In Jaco de Bakker and Jan van Leeuwen, editors, Automata, Languages and Programming, volume 85 of Lecture Notes in Computer Science, pages 422-435. Springer Berlin Heidelberg, 1980. Google Scholar
  18. Marcel Paul Schützenberger. On finite monoids having only trivial subgroups. Information and Control, 8(2):190-194, 1965. Google Scholar
  19. Howard Straubing. Finite Automata, Formal Logic, and Circuit Complexity. Birkhäuser, Boston, 1994. Google Scholar
  20. H. Venkateswaran. Properties that characterize LOGCFL. J. Comput. Syst. Sci., 43(2):380-404, 1991. Google Scholar
  21. Heribert Vollmer. Introduction to circuit complexity - a uniform approach. Texts in theoretical computer science. Springer, 1999. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact