The AC^0-complexity of visibly pushdown languages

DOI10.4230/LIPICS.STACS.2024.38MaRDI QIDQ6902684zbMATH OpenFDO

Authors Stefan Göller, Nathan Grosshans

Publication date 10 November 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.STACS.2024.38

zbMATH Keywords

AC0circuit complexityvisibly pushdown languages

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A Brief History of Strahler Numbers
• A logic for constant-depth circuits
• Automata, Languages and Programming
• Boolean function complexity. Advances and frontiers.
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Constant Depth Reducibility
• scientific article; zbMATH DE number 5872386 (Why is no real title available?)
• scientific article; zbMATH DE number 3696500 (Why is no real title available?)
• scientific article; zbMATH DE number 3639163 (Why is no real title available?)
• scientific article; zbMATH DE number 1254648 (Why is no real title available?)
• scientific article; zbMATH DE number 618821 (Why is no real title available?)
• Languages that Capture Complexity Classes
• On finite monoids having only trivial subgroups
• Regular languages in \(NC\)
• Regularity Problems for Visibly Pushdown Languages
• Visibly counter languages and constant depth circuits
• Visibly pushdown languages

Cited in

(1)

• More on language families with a decidable pumping-problem (extended abstract)

This page was built for publication: The \(\text{AC}^0\)-complexity of visibly pushdown languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6902684)