Comments on ``Arithmetic complexity, Kleene closure, and formal power series

DOI10.1007/s00224-013-9471-2zbMath1286.68164OpenAlexW2082636016MaRDI QIDQ372962

V. Arvind, Meena Mahajan, Eric W. Allender

Publication date: 21 October 2013

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-013-9471-2

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (1)

The complexity of the characteristic and the minimal polynomial.

Cites Work

• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Arithmetic complexity, Kleene closure, and formal power series
• Finite monoids and the fine structure of NC ¹

This page was built for publication: Comments on ``Arithmetic complexity, Kleene closure, and formal power series