Eric Allender, Ian Mertz

We give complexity bounds for various classes of functions computed by cost register automata.

more >>>Eric Allender, Andreas Krebs, Pierre McKenzie

Cost register automata (CRA) 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 semiring (N,min,+) can simulate polynomial time computation, proving along ... more >>>