Circuits and Expressions over Finite Semirings
Moses Ganardi, Danny Hucke, Daniel König, Markus Lohrey · ACM Transactions on Computation Theory · 2018
The computational complexity of the circuit and expression evaluation problem for finite semirings is considered, where semirings are not assumed to have an additive or a multiplicative identity. The following dichotomy is shown: If a finite semiring is such that (i) the multiplicative semigroup is solvable and (ii) it does not contain a subsemiring with an additive identity 0 and a multiplicative identity 1 ≠ 0, then the circuit evaluation problem is in DET ⊆ NC 2 , and the expression evaluation problem for the semiring is in TC 0 . For all other finite semirings, the circuit evaluation problem is P-complete and the expression evaluation problem is NC 1 -complete. As an application, we determine the complexity of intersection non-emptiness problems for given context-free grammars (regular expressions) with a fixed regular language.