Allender, Eric & Krebs, Andreas & McKenzie, Pierre (2018). Better Complexity Bounds for Cost Register Automata. Theory of Computing Systems Retrieved from https://doi.org/doi:10.7282/T38K7DGB
AbstractCost 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.
RightsCopyright for scholarly resources published in RUcore is retained by the copyright holder. By virtue of its appearance in this open access medium, you are free to use this resource, with proper attribution, in educational and other non-commercial settings. Other uses, such as reproduction or republication, may require the permission of the copyright holder.
