TY - GEN

T1 - Better complexity bounds for cost register automata

AU - Allender, Eric

AU - Krebs, Andreas

AU - McKenzie, Pierre

N1 - Funding Information:
∗ Supported by NSF grant CCF-1555409 (Allender), by the DFG Emmy-Noether program KR 4042/2 (Krebs), and by the Natural Sciences and Engineering Research Council of Canada (McKenzie)
Publisher Copyright:
© Eric Allender, Andreas Krebs, and Pierre McKenzie; licensed under Creative Commons License CC-BY.

PY - 2017/11/1

Y1 - 2017/11/1

N2 - 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 (N U [{∞}, min, +) can simulate polynomial time computation, proving along the way that a naturally defined 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 NC1 when the semiring is (z,+,x) or (γ[U{ω}, max, 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 NC1 versus GapNC1.

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 (N U [{∞}, min, +) can simulate polynomial time computation, proving along the way that a naturally defined 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 NC1 when the semiring is (z,+,x) or (γ[U{ω}, max, 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 NC1 versus GapNC1.

KW - Computational complexity

KW - Cost registers

UR - http://www.scopus.com/inward/record.url?scp=85038442246&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85038442246&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.MFCS.2017.24

DO - 10.4230/LIPIcs.MFCS.2017.24

M3 - Conference contribution

AN - SCOPUS:85038442246

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017

A2 - Larsen, Kim G.

A2 - Raskin, Jean-Francois

A2 - Bodlaender, Hans L.

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017

Y2 - 21 August 2017 through 25 August 2017

ER -