Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with P-completeness:
TR17-072 | 25th April 2017
Eric Allender, Andreas Krebs, Pierre McKenzie

Better Complexity Bounds for Cost Register Machines

Revisions: 1

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 >>>

ISSN 1433-8092 | Imprint