Arithmetic Circuits, Monomial Algebras and Finite Automata

DOI10.1007/978-3-642-03816-7_8zbMath1250.68116OpenAlexW1602110529MaRDI QIDQ3182914

Pushkar S. Joglekar, V. Arvind

Publication date: 16 October 2009

Published in: Mathematical Foundations of Computer Science 2009 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-03816-7_8

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Unnamed Item
• Matching is as easy as matrix inversion
• Which problems have strongly exponential complexity?
• Deterministic polynomial identity testing in non-commutative models
• Greibach normal form transformation revisited.
• Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size
• Some Exact Complexity Results for Straight-Line Computations over Semirings
• Efficient string matching
• Randomness efficient identity testing of multivariate polynomials
• Matrix Equations and Normal Forms for Context-Free Grammars
• Derandomizing polynomial identity tests means proving circuit lower bounds

This page was built for publication: Arithmetic Circuits, Monomial Algebras and Finite Automata