ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > KEYWORD > ALGEBRAIC BRANCHING PROGRAM:
Reports tagged with Algebraic Branching Program:
TR09-026 | 17th February 2009
Vikraman Arvind, Pushkar Joglekar

Arithmetic Circuit Size, Identity Testing, and Finite Automata

Let $\F\{x_1,x_2,\cdots,x_n\}$ be the noncommutative polynomial
ring over a field $\F$, where the $x_i$'s are free noncommuting
formal variables. Given a finite automaton $\A$ with the $x_i$'s as
alphabet, we can define polynomials $\f( mod A)$ and $\f(div A)$
obtained by natural operations that we call ... more >>>




ISSN 1433-8092 | Imprint