@article{Allender:2019wa,
    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 {\$}({$\backslash$}mathbb {\{}N{\}}{$\backslash$}cup {$\backslash$}{\{}{$\backslash$}infty {$\backslash$}{\}},{$\backslash$}min ,+){\$}can simulate polynomial time computation, proving along the way that a naturally defined width-k circuit value problem over the tropical semiring is {\$}{$\backslash$}textsf {\{}P{\}}{\$}-complete. Then the copyless variant of the CRA, requiring that semiring operations be applied to distinct registers, is shown no more powerful than {\$}{$\backslash$}textsf {\{}NC{\}}\^{}{\{}1{\}}{\$}when the semiring is {\$}({$\backslash$}mathbb {\{}Z{\}},+,{$\backslash$}times ){\$}or {\$}({\{}{$\backslash$}Gamma {\}}\^{}{\{}*{\}}{$\backslash$}cup {$\backslash$}{\{}{$\backslash$}bot {$\backslash$}{\}},{$\backslash$}max ,{$\backslash$}text {\{}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 {\$}{$\backslash$}textsf {\{}NC{\}}{\$}versus {\$}{$\backslash$}textsf {\{}P{\}}{\$}and NC1 versus GapNC1.},
    Author = {Allender, Eric and Krebs, Andreas and McKenzie, Pierre},
    Date = {2019/04/01},
    File = {Better Complexity Bounds for Cost Register Automata - Allender2019\_Article\_BetterComplexityBoundsForCostR.pdf},
    ISBN = {1433-0490},
    Journal = {Theory of Computing Systems},
    Number = {3},
    Pages = {367--385},
    Title = {Better Complexity Bounds for Cost Register Automata},
    URL = {https://doi.org/10.1007/s00224-018-9871-4},
    Volume = {63},
    Year = {2019},
    bdsk-url-1 = {https://doi.org/10.1007/s00224-018-9871-4},
    date-added = {2021-11-23 15:03:13 +0100},
    date-modified = {2021-11-23 15:03:14 +0100},
    id = {Allender2019},
    doi = {10.1007/s00224-018-9871-4}
}

@article{Allender:2019wa, 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 {\$}({$\backslash$}mathbb {{}N{}}{$\backslash$}cup {$\backslash$}{{}{$\backslash$}infty {$\backslash$}{}},{$\backslash$}min ,+){\$}can simulate polynomial time computation, proving along the way that a naturally defined width-k circuit value problem over the tropical semiring is {\$}{$\backslash$}textsf {{}P{}}{\$}-complete. Then the copyless variant of the CRA, requiring that semiring operations be applied to distinct registers, is shown no more powerful than {\$}{$\backslash$}textsf {{}NC{}}\^{}{{}1{}}{\$}when the semiring is {\$}({$\backslash$}mathbb {{}Z{}},+,{$\backslash$}times ){\$}or {\$}({{}{$\backslash$}Gamma {}}\^{}{{}*{}}{$\backslash$}cup {$\backslash$}{{}{$\backslash$}bot {$\backslash$}{}},{$\backslash$}max ,{$\backslash$}text {{}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 {\$}{$\backslash$}textsf {{}NC{}}{\$}versus {\$}{$\backslash$}textsf {{}P{}}{\$}and NC1 versus GapNC1.}, Author = {Allender, Eric and Krebs, Andreas and McKenzie, Pierre}, Date = {2019/04/01}, File = {Better Complexity Bounds for Cost Register Automata - Allender2019_Article_BetterComplexityBoundsForCostR.pdf}, ISBN = {1433-0490}, Journal = {Theory of Computing Systems}, Number = {3}, Pages = {367--385}, Title = {Better Complexity Bounds for Cost Register Automata}, URL = {https://doi.org/10.1007/s00224-018-9871-4}, Volume = {63}, Year = {2019}, bdsk-url-1 = {https://doi.org/10.1007/s00224-018-9871-4}, date-added = {2021-11-23 15:03:13 +0100}, date-modified = {2021-11-23 15:03:14 +0100}, id = {Allender2019}, doi = {10.1007/s00224-018-9871-4} }