TY - JOUR
TI - Better Complexity Bounds for Cost Register Automata
DO - https://doi.org/doi:10.7282/T38K7DGB
AU - Allender, Eric
AU - Krebs, Andreas
AU - McKenzie, Pierre
PY - 2018
T2 - Theory of Computing Systems
AB - 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 NC^1 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 NC^1 versus GapNC^1.
KW - Circuit Complexity
KW - P-completeness
KW - Cost-Register Automata
LA - English
ER -