Circuits and Expressions over Finite Semirings
| Autor: | Danny Hucke, Markus Lohrey, Daniel König, Moses Ganardi |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Pure mathematics
Computational complexity theory Semigroup 010102 general mathematics Multiplicative function 0102 computer and information sciences 01 natural sciences Expression (mathematics) Theoretical Computer Science Semiring TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES Computational Theory and Mathematics Regular language 010201 computation theory & mathematics ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION Regular expression Additive identity 0101 mathematics Mathematics |
| Zdroj: | ACM Transactions on Computation Theory. 10:1-30 |
| ISSN: | 1942-3462 1942-3454 |
| DOI: | 10.1145/3241375 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|