Abstract
Cost register automata (CRAs) are one-way finite automata whose transitions have the side-effect that a register is set to the result of applying a state-dependent semiring operation to a pair of registers. Here it is shown that CRAs over the tropical semiring can simulate polynomial time computation, proving along the way that a naturally dened width-k circuit value problem over the tropical semiring is P-complete. Then the copyless variant of the CRA, requiring that semiring operations be applied to distinct registers, is shown no more powerful than NC1 when the semiring is the integers, or strings with operations max and concat. This relates questions left open in recent work on the complexity of CRA-computable functions to long-standing class separation conjectures in complexity theory, such as NC versus P and NC1 versus GapNC1.