Name
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 \((\mathbb {N}\cup \{\infty \},\min ,+)\) can simulate polynomial time computation, proving along the way that a naturally defined width-k circuit value problem over the tropical semiring is \(\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 \(\textsf {NC}^{1}\) when the semiring is \((\mathbb {Z},+,\times )\) or \(({\Gamma }^{*}\cup \{\bot \},\max ,\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 \(\textsf {NC}\) versus \(\textsf {P}\) and NC1 versus GapNC1. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1007/s00224-018-9871-4 | MFCS |
Keywords | Field | DocType |
Computational complexity, Circuit complexity, Cost register automata, Arithmetic circuits, Tropical semiring | Discrete mathematics,Arithmetic circuits,Combinatorics,Circuit complexity,Automaton,Finite-state machine,Time complexity,Mathematics,Semiring,Computation,Computational complexity theory | Conference |
Volume | Issue | ISSN |
63 | 3 | 1433-0490 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Eric Allender | 1 | 1434 | 121.38 |
| Andreas Krebs | 2 | 21 | 8.20 |
| Pierre McKenzie | 3 | 100 | 12.29 |