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 \emph{intersecting} and \emph{quotienting} the ... more >>>



ISSN 1433-8092 | Imprint