Two function algebras defining functions in \(\mathsf{NC}^k\) Boolean circuits

DOI10.1016/j.ic.2015.12.009zbMath1339.68096OpenAlexW2231425046MaRDI QIDQ276257

Guillaume Bonfante, Jean-Yves Marion, Reinhard Kahle, Isabel Oitavem

Publication date: 3 May 2016

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2015.12.009

zbMATH Keywords

transducersBoolean circuits\(\mathsf{NC}^k\)parallel computation class

Mathematics Subject Classification ID

Related Items (2)

\textsc{ComplexityParser}: an automatic tool for certifying poly-time complexity of Java programs ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The realm of primitive recursion
• On uniform circuit complexity
• A new recursion-theoretic characterization of the polytime functions
• Light linear logic
• Function-algebraic characterizations of log and polylog parallel time
• A characterization of alternating log time by ramified recurrence
• On tiered small jump operators
• Alternation
• Paths, Trees, and Flowers
• Uniform Circuits, & Boolean Proof Nets
• On Relations Defined by Generalized Finite Automata
• Computational Complexity

This page was built for publication: Two function algebras defining functions in \(\mathsf{NC}^k\) Boolean circuits